DEV Community

Cover image for LeetCode Challenge: 3. Longest Substring Without Repeating Characters - JavaScript Solution πŸš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

2 1 1 1 1

LeetCode Challenge: 3. Longest Substring Without Repeating Characters - JavaScript Solution πŸš€

Top Interview 150

The Longest Substring Without Repeating Characters problem is a classic sliding window problem that tests your ability to efficiently manage substrings. Let’s solve LeetCode 3 step by step.


πŸš€ Problem Description

Given a string s, return the length of the longest substring without repeating characters.

πŸ’‘ Examples

Example 1

Input: s = "abcabcbb"  
Output: 3  
Explanation: The answer is "abc", with a length of 3.
Enter fullscreen mode Exit fullscreen mode

Example 2

Input: s = "bbbbb"  
Output: 1  
Explanation: The answer is "b", with a length of 1.
Enter fullscreen mode Exit fullscreen mode

Example 3

Input: s = "pwwkew"  
Output: 3  
Explanation: The answer is "wke", with a length of 3.
Enter fullscreen mode Exit fullscreen mode

πŸ† JavaScript Solution

We will use the sliding window technique to track the current substring and a Set to ensure there are no duplicate characters.

Sliding Window Implementation

var lengthOfLongestSubstring = function(s) {
    let maxLength = 0;
    let left = 0;
    const seen = new Set();

    for (let right = 0; right < s.length; right++) {
        while (seen.has(s[right])) {
            seen.delete(s[left]);
            left++;
        }

        seen.add(s[right]);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
};
Enter fullscreen mode Exit fullscreen mode

πŸ” How It Works

  1. Sliding Window:

    • Use two pointers (left and right) to represent the current substring.
    • The right pointer expands the window by including characters.
    • The left pointer shrinks the window to eliminate duplicate characters.
  2. Set for Uniqueness:

    • Use a Set to store characters in the current substring.
    • If a duplicate is found, remove characters from the left until the duplicate is removed.
  3. Update Maximum Length:

    • Calculate the substring length as right - left + 1 and update maxLength.

πŸ”‘ Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string.

    • Each character is added and removed from the Set at most once.
  • Space Complexity: O(k), where k is the size of the character set (e.g., 26 for lowercase English letters).


πŸ“‹ Dry Run

Input: s = "abcabcbb"
Dry Run
Output: 3


Alternative: Optimized Sliding Window with Hash Map
Instead of using a Set, a hash map can track the last index of each character.


Optimized Implementation

var lengthOfLongestSubstring = function(s) {
    let maxLength = 0;
    let left = 0;
    const charIndexMap = {};

    for (let right = 0; right < s.length; right++) {
        if (charIndexMap[s[right]] !== undefined && charIndexMap[s[right]] >= left) {
            left = charIndexMap[s[right]] + 1;
        }

        charIndexMap[s[right]] = right;
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
};
Enter fullscreen mode Exit fullscreen mode

πŸ”‘ Complexity Analysis (Optimized Version)

  • Time Complexity: O(n), as each character is processed once.
  • Space Complexity: O(k), where k is the size of the character set.

πŸ“š Learn More

Check out the full explanation and code walkthrough on my previous Dev.to post:
πŸ‘‰ Minimum Size Subarray Sum - JavaScript Solution

Which sliding window implementation do you prefer? Let’s discuss below! πŸš€


Study

Image of Datadog

How to Diagram Your Cloud Architecture

Cloud architecture diagrams provide critical visibility into the resources in your environment and how they’re connected. In our latest eBook, AWS Solution Architects Jason Mimick and James Wenzel walk through best practices on how to build effective and professional diagrams.

Download the Free eBook

Top comments (1)

Collapse
 
rahulgithubweb profile image
Rahul Kumar Barnwal β€’

Follow Me on GitHub πŸš€

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!

Sentry image

See why 4M developers consider Sentry, β€œnot bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more