Longest Substring Without Repeating Characters

Problem Statement

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

Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

Approach: Sliding Window

We can use a sliding window approach with a Hash Set to keep track of characters we have seen in our current window.

1. Initialize two pointers, left and right, both at index 0. These represent our current sliding window.
2. Use a Set to keep track of characters currently in the window.
3. Keep track of the maximum length found so far (maxLength), initialized to 0.
4. While right is less than the length of the string:
   • If the character at s[right] is not in the set:
     • Add the character to the set.
     • Update maxLength if the current window size (right - left + 1) is larger.
     • Increment right to expand the window.
   • If the character at s[right] is already in the set:
     • We found a duplicate! We must shrink our window from the left until the duplicate character is removed.
     • Remove the character at s[left] from the set.
     • Increment left to shrink the window.
5. Return the maxLength.

Solution

/**
 * @param {string} s
 * @return {number}
 */
function lengthOfLongestSubstring(s) {
    const seen = new Set();
    let left = 0;
    let right = 0;
    let maxLength = 0;
    
    while (right < s.length) {
        if (!seen.has(s[right])) {
            seen.add(s[right]);
            maxLength = Math.max(maxLength, right - left + 1);
            right++;
        } else {
            seen.delete(s[left]);
            left++;
        }
    }
    
    return maxLength;
}

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the length of the string. In the worst case, each character is visited at most twice (once by right and once by left).
• Space Complexity: $O(\min(n, m))$ where $m$ is the size of the character set (e.g., 26 for lowercase English letters, but could be larger depending on the allowed characters). We store at most this many elements in the Hash Set.