Problem Description

Given a string s, you need to find the length of the longest substring that contains no duplicate characters.

A substring is a contiguous sequence of characters within the string. For example, in the string "abcabcbb", some substrings include "abc", "bca", "cab", etc.

The task is to identify the longest possible substring where every character appears at most once (no repeating characters), and return its length.

For instance:

• If s = "abcabcbb", the longest substring without repeating characters is "abc", which has length 3
• If s = "bbbbb", the longest substring without repeating characters is "b", which has length 1
• If s = "pwwkew", the longest substring without repeating characters is "wke", which has length 3

The solution uses a sliding window technique with two pointers (l and r) to maintain a window of non-repeating characters. A counter tracks character occurrences within the current window. When a duplicate is found (count > 1), the left pointer moves right until the duplicate is removed. The maximum window size encountered during this process is the answer.

Intuition

When looking for the longest substring without repeating characters, we need to examine different portions of the string. A naive approach would check every possible substring, but this would be inefficient.

The key insight is that once we find a valid substring (with no repeating characters), we can extend it by adding characters to the right as long as they don't create duplicates. When we encounter a duplicate, we don't need to start over completely - we just need to shrink our window from the left until the duplicate is removed.

Think of it like a sliding window that expands and contracts as needed. We keep expanding the window to the right by including new characters. When we hit a duplicate, instead of abandoning the entire window, we contract from the left just enough to eliminate the conflict. This way, we maintain the longest valid window possible at each step.

For example, with string "abcabcbb":

• Start with window "a", then expand to "ab", then "abc"
• When we hit the second 'a', we have "abca" which is invalid
• Instead of restarting, we shrink from left: remove first 'a' to get "bca"
• Continue this process, always tracking the maximum window size seen

Using a counter to track character frequencies within our window makes it easy to detect duplicates - when any character's count exceeds 1, we know there's a repeat. The two-pointer technique with l (left) and r (right) naturally implements this sliding window, where r - l + 1 gives us the current window size.

This approach ensures we examine each character at most twice (once when expanding right, once when contracting left), making it much more efficient than checking all possible substrings.

Learn more about Sliding Window patterns.

Solution Approach

The solution implements a sliding window approach using two pointers to efficiently find the longest substring without repeating characters.

Data Structures Used:

• A Counter (hash table) cnt to track the frequency of each character in the current window
• Two pointers: l (left boundary) and r (right boundary) of the sliding window
• Variable ans to store the maximum length found

Algorithm Steps:

1. Initialize the window: Start with an empty Counter cnt, set both the answer ans and left pointer l to 0.

2. Expand the window: Iterate through the string using enumerate(s) where r is the index (right pointer) and c is the current character.

3. Add character to window: For each character s[r], increment its count in the Counter: cnt[c] += 1

4. Handle duplicates: When cnt[c] > 1, it means the current character creates a duplicate in the window. We need to shrink the window from the left:

   while cnt[c] > 1:
       cnt[s[l]] -= 1  # Remove leftmost character from count
       l += 1           # Move left pointer right

   This loop continues until the duplicate is eliminated (when cnt[c] becomes 1).

5. Update maximum length: After ensuring no duplicates exist in the current window [l, r], calculate the window size as r - l + 1 and update the answer: ans = max(ans, r - l + 1)

6. Return result: After processing all characters, return ans as the length of the longest substring without repeating characters.

Time Complexity: O(n) where n is the length of the string. Each character is visited at most twice (once by the right pointer and once by the left pointer).

Space Complexity: O(min(m, n)) where m is the size of the character set. The Counter stores at most min(size of character set, n) characters.

Example Walkthrough

Let's walk through the solution with the string s = "pwwkew".

Initial Setup:

• cnt = {} (empty counter)
• l = 0 (left pointer)
• ans = 0 (maximum length)

Step-by-step execution:

Iteration 1: r=0, c='p'

• Add 'p' to window: cnt = {'p': 1}
• No duplicate (cnt['p'] = 1)
• Window is "p" (indices 0 to 0)
• Update ans: ans = max(0, 0-0+1) = 1

Iteration 2: r=1, c='w'

• Add 'w' to window: cnt = {'p': 1, 'w': 1}
• No duplicate (cnt['w'] = 1)
• Window is "pw" (indices 0 to 1)
• Update ans: ans = max(1, 1-0+1) = 2

Iteration 3: r=2, c='w'

• Add 'w' to window: cnt = {'p': 1, 'w': 2}
• Duplicate detected! (cnt['w'] = 2)
• Shrink window from left:
  • Remove s[0]='p': cnt = {'p': 0, 'w': 2}, l = 1
  • Remove s[1]='w': cnt = {'p': 0, 'w': 1}, l = 2
  • Now cnt['w'] = 1, stop shrinking
• Window is "w" (indices 2 to 2)
• Update ans: ans = max(2, 2-2+1) = 2

Iteration 4: r=3, c='k'

• Add 'k' to window: cnt = {'p': 0, 'w': 1, 'k': 1}
• No duplicate (cnt['k'] = 1)
• Window is "wk" (indices 2 to 3)
• Update ans: ans = max(2, 3-2+1) = 2

Iteration 5: r=4, c='e'

• Add 'e' to window: cnt = {'p': 0, 'w': 1, 'k': 1, 'e': 1}
• No duplicate (cnt['e'] = 1)
• Window is "wke" (indices 2 to 4)
• Update ans: ans = max(2, 4-2+1) = 3

Iteration 6: r=5, c='w'

• Add 'w' to window: cnt = {'p': 0, 'w': 2, 'k': 1, 'e': 1}
• Duplicate detected! (cnt['w'] = 2)
• Shrink window from left:
  • Remove s[2]='w': cnt = {'p': 0, 'w': 1, 'k': 1, 'e': 1}, l = 3
  • Now cnt['w'] = 1, stop shrinking
• Window is "kew" (indices 3 to 5)
• Update ans: ans = max(3, 5-3+1) = 3

Final Result: The longest substring without repeating characters has length 3 (corresponding to "wke" or "kew").

Solution Implementation

Time and Space Complexity

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

The algorithm uses a sliding window approach with two pointers (l and r). The right pointer r iterates through each character in the string exactly once via the enumerate loop. The left pointer l also moves through the string, but each character is visited at most twice - once when the right pointer includes it in the window and at most once when the left pointer removes it from the window. Since each character is processed a constant number of times, the overall time complexity is linear.

Space Complexity: O(min(n, |Σ|)) or more precisely O(|Σ|), where |Σ| represents the size of the character set.

The Counter dictionary cnt stores the frequency of characters in the current window. In the worst case, the dictionary can contain all unique characters from the string. For ASCII characters, |Σ| = 128 (or 256 for extended ASCII). For Unicode characters, this could be larger. However, the space used is bounded by both the size of the character set and the length of the string, hence O(min(n, |Σ|)). Since the character set size is typically considered constant (like 128 for ASCII), the space complexity is effectively O(1) or O(|Σ|) where |Σ| = 128 for standard ASCII characters.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to Handle Empty String

Issue: The code doesn't explicitly check for empty strings. While the current implementation handles it correctly (returns 0), not being aware of edge cases can lead to issues in modified versions.

Example:

s = ""  # Should return 0

Solution: While the current code handles this implicitly, you can add an explicit check for clarity:

if not s:
    return 0

Pitfall 2: Inefficient Character Removal from Counter

Issue: Using Counter with decrement operations doesn't automatically remove keys with zero count, potentially leading to memory inefficiency with very long strings.

Example:

# After cnt[s[left]] -= 1, if count becomes 0, the key still exists in Counter
# This can accumulate unnecessary keys over time

Solution: Clean up zero-count entries:

while char_count[char] > 1:
    char_count[s[left]] -= 1
    if char_count[s[left]] == 0:
        del char_count[s[left]]  # Remove key when count reaches 0
    left += 1

Pitfall 3: Using Regular Dictionary Instead of Counter

Issue: Attempting to increment a non-existent key in a regular dictionary causes KeyError.

Wrong approach:

char_count = {}  # Regular dict instead of Counter
char_count[char] += 1  # KeyError if char not in dict

Solution: Either use Counter or handle dictionary initialization:

# Option 1: Use Counter (recommended)
char_count = Counter()

# Option 2: Use regular dict with get()
char_count = {}
char_count[char] = char_count.get(char, 0) + 1

Pitfall 4: Off-by-One Error in Window Size Calculation

Issue: Incorrectly calculating window size as right - left instead of right - left + 1.

Wrong calculation:

max_length = max(max_length, right - left)  # Missing +1

Solution: Always remember that for a window from index left to right (inclusive), the size is:

window_size = right - left + 1

Pitfall 5: Not Understanding When to Update Maximum Length

Issue: Updating the maximum length before ensuring the window is valid (no duplicates).

Wrong sequence:

for right, char in enumerate(s):
    char_count[char] += 1
    max_length = max(max_length, right - left + 1)  # Wrong: updating before removing duplicates
    while char_count[char] > 1:
        char_count[s[left]] -= 1
        left += 1

Solution: Always update the maximum length after ensuring the window contains no duplicates:

for right, char in enumerate(s):
    char_count[char] += 1
    while char_count[char] > 1:  # First: ensure no duplicates
        char_count[s[left]] -= 1
        left += 1
    max_length = max(max_length, right - left + 1)  # Then: update maximum