Longest Substring Without Repeating Characters

Difficulty: Medium | Acceptance: 37.43% | Paid: No

Topics: Hash Table, String, Sliding Window

• Examples
• Constraints
• Brute Force with Nested Loops
• Sliding Window with HashSet
• Optimized Sliding Window with HashMap

Examples

Input

s = "abcabcbb"

Output

3

Explanation

The answer is “abc”, with the length of 3.

Input

s = "bbbbb"

Output

1

Explanation

The answer is “b”, with the length of 1.

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.

Constraints

- 0 <= s.length <= 5 * 10^4
- s consists of English letters, digits, symbols and spaces.

Brute Force with Nested Loops

Intuition

The most straightforward approach is to examine each possible substring and check if it has all unique characters. We can iterate through all substrings using nested loops and keep track of the maximum length found.

Steps

• Use two nested loops: the outer loop marks the start of a substring, and the inner loop extends the substring.
• For each substring, keep a set of characters to check for duplicates. If a duplicate is found, break and move to the next starting position.
• Track the maximum length of substrings without repeating characters encountered.

def lengthOfLongestSubstring(s: str) -> int:
    n = len(s)
    max_length = 0
    
    for i in range(n):
        char_set = set()
        for j in range(i, n):
            if s[j] in char_set:
                break
            char_set.add(s[j])
            max_length = max(max_length, j - i + 1)
    
    return max_length

Complexity

• Time: O(n^3), where n is the length of the string. The nested loops contribute O(n^2), and for each substring, checking for duplicates takes O(n).
• Space: O(min(m,n)), where m is the size of the character set. In the worst case, the set stores all unique characters of the string.
• Notes: This brute-force approach is inefficient due to the repeated work of checking substrings. It’s useful for understanding the problem but not suitable for large inputs.

Sliding Window with HashSet

Intuition

To optimize, we can use a sliding window technique. We maintain a window that represents the current substring without repeating characters. As we expand the window to the right, if we encounter a duplicate, we shrink it from the left until the duplicate is removed.

Steps

• Initialize two pointers, left and right, to represent the window boundaries. Start with both at index 0.
• Use a HashSet to keep track of characters in the current window. As we move the right pointer, add characters to the set.
• If the character at the right pointer is already in the set, move the left pointer and remove characters from the set until the duplicate is gone.
• Keep track of the maximum window size encountered during this process.

def lengthOfLongestSubstring(s: str) -> int:
    n = len(s)
    char_set = set()
    left = 0
    max_length = 0
    
    for right in range(n):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
    
    return max_length

Complexity

• Time: O(2n) = O(n), where n is the length of the string. In the worst case, each character will be visited twice by the left and right pointers.
• Space: O(min(m,n)), where m is the size of the character set. The space used by the HashSet is bounded by the size of the character set.
• Notes: This approach is significantly more efficient than the brute-force method. It’s a classic example of the sliding window technique, which is widely used in substring problems.

Optimized Sliding Window with HashMap

Intuition

We can further optimize the sliding window approach by using a HashMap to store the last index of each character. This allows us to jump the left pointer directly to the correct position when a duplicate is found, avoiding unnecessary iterations.

Steps

• Initialize two pointers, left and right, and a HashMap to store the last seen index of each character.
• Iterate through the string with the right pointer. For each character, check if it’s in the HashMap and its last seen index is within the current window.
• If so, move the left pointer to the maximum of its current position and one position after the last occurrence of the current character.
• Update the character’s last seen index in the HashMap and update the maximum length if the current window is larger.

def lengthOfLongestSubstring(s: str) -> int:
    n = len(s)
    char_index_map = {}
    left = 0
    max_length = 0
    
    for right in range(n):
        if s[right] in char_index_map and char_index_map[s[right]] >= left:
            left = char_index_map[s[right]] + 1
        char_index_map[s[right]] = right
        max_length = max(max_length, right - left + 1)
    
    return max_length

Complexity

• Time: O(n), where n is the length of the string. We iterate through the string once, and each character is processed at most twice (once by right pointer, once by left pointer).
• Space: O(min(m,n)), where m is the size of the character set. The space used by the HashMap is bounded by the size of the character set.
• Notes: This is the optimal solution for this problem. It’s a significant improvement over the previous sliding window approach, especially for strings with long repeated sequences. The key insight is using the HashMap to make large jumps when duplicates are found.