3. Longest Substring Without Repeating Characters Medium

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

Input: A string s

Output: Return the length of the longest substring within it that does not contain duplicate characters.

This problem falls under the Variable-length Sliding Window category.

We can use two pointers (left and right) to maintain a sliding window, and a set to keep track of the characters that have appeared in the current window. Each time the right pointer moves to the right to expand the window, we check if the newly added character is already present in the window:

• If it is not a duplicate, add the character to the set and update the current maximum substring length.
• If it is a duplicate character, repeatedly move the left pointer to shrink the window until the duplicate character is removed.

Throughout this process, we maintain the uniqueness of characters inside the window and record the maximum length, which is finally returned.

Implementation

python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = set()      # Used to store characters present in the current window
        left = 0          # Left boundary of the sliding window
        max_len = 0       # Records the max length of substring (without duplicates)

        # Iterate through string, moving right pointer 'right' each time to expand window
        for right in range(len(s)):
            # If the character pointed to by right pointer already exists in the current window
            # Constantly move left pointer to shrink window, until the duplicate character is removed
            while s[right] in seen:
                seen.remove(s[left])  # Remove left boundary character
                left += 1             # Move left pointer rightwards, shrink window

            # Add current character to window (After duplicates are gone)
            seen.add(s[right])

            # Update max length (Window length = right - left + 1)
            max_len = max(max_len, right - left + 1)

        return max_len  # Return the max length of substring without duplicate characters

javascript

const lengthOfLongestSubstring = function(s) {
    const seen = new Set(); // Used to store characters present in the current window
    let left = 0; // Left boundary of the sliding window
    let maxLen = 0; // Records the max length of substring (without duplicates)

    // Iterate through string, moving right pointer 'right' each time to expand window
    for (let right in s) {
        // If the character pointed to by right pointer already exists in the current window
        // Constantly move left pointer to shrink window, until the duplicate character is removed
        while (seen.has(s[right])) {
            // Remove left boundary character
            seen.delete(s[left]);
            // Move left pointer rightwards, shrink window
            left += 1;
        }

        // Add current character to window (After duplicates are gone)
        seen.add(s[right]);
        // Update max length (Window length = right - left + 1)
        maxLen = Math.max(maxLen, right - left + 1);
    }

    // Return the max length of substring without duplicate characters
    return maxLen;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1) or O(MIN(m, n)) where m is size of alphabet and n is length of string

Links

3. Longest Substring Without Repeating Characters (English)3. 无重复字符的最长子串 (Chinese)