Problem Description

You are given a string s. Your task is to find the length of the longest substring that contains at most two distinct characters.

A substring is a contiguous sequence of characters within the string. For example, in the string "eceba", some substrings include "e", "ec", "ece", "eceb", and "eceba".

The constraint is that the substring can have at most 2 different characters. This means the substring can contain:

• Only 1 distinct character (like "aaa" or "bbb")
• Exactly 2 distinct characters (like "aabbb" or "ececec")

For example:

• If s = "eceba", the longest valid substring is "ece" which has length 3 (contains only characters 'e' and 'c')
• If s = "ccaabbb", the longest valid substring is "aabbb" which has length 5 (contains only characters 'a' and 'b')

The solution uses a sliding window approach with two pointers. It maintains a counter to track the frequency of characters in the current window. When the window contains more than 2 distinct characters, it shrinks from the left by moving the left pointer j forward and decreasing character counts. The maximum window size encountered during this process is the answer.

Intuition

When we need to find the longest substring with a specific constraint, the sliding window technique often comes to mind. The key insight here is that we want to maintain a "valid" window that satisfies our constraint (at most 2 distinct characters) while maximizing its size.

Think of it like a flexible window that can expand and contract. We start with an empty window and gradually expand it by adding characters from the right. As long as we have at most 2 distinct characters, we can keep expanding to explore longer substrings.

The critical moment comes when adding a new character would violate our constraint (giving us more than 2 distinct characters). At this point, we can't simply skip this character because we need to check all possible substrings. Instead, we need to shrink our window from the left until it becomes valid again.

Why shrink from the left? Because we're systematically exploring all possibilities by moving through the string from left to right. By removing characters from the left side of our window, we're essentially saying "let's try a new substring that starts a bit later in the string."

The beauty of this approach is that we never need to check the same substring twice. Each position in the string is visited at most twice - once when expanding the window (adding it) and once when contracting the window (removing it). This gives us an efficient O(n) solution.

We use a frequency counter to track which characters are in our current window and how many times each appears. When a character's count drops to 0, we remove it from our counter entirely, allowing us to easily check if we have at most 2 distinct characters by checking the counter's size.

Solution Approach

The implementation uses a sliding window technique with two pointers to efficiently find the longest substring with at most two distinct characters.

Data Structures Used:

• A Counter (hash map) to track the frequency of each character in the current window
• Two pointers: j (left boundary) and i (right boundary, implicit in the enumeration)

Algorithm Steps:

1. Initialize variables:

   • cnt = Counter() - tracks character frequencies in current window
   • ans = 0 - stores the maximum length found
   • j = 0 - left pointer of the sliding window

2. Expand the window: Iterate through each character in the string using enumerate(s):

   • Add the current character c to the window by incrementing cnt[c]
   • The right boundary of the window is at position i

3. Contract when necessary: When the window becomes invalid (more than 2 distinct characters):

   while len(cnt) > 2:
       cnt[s[j]] -= 1
       if cnt[s[j]] == 0:
           cnt.pop(s[j])
       j += 1

   • Decrease the count of the leftmost character s[j]
   • If its count becomes 0, remove it from the counter entirely
   • Move the left pointer j forward
   • Continue until we have at most 2 distinct characters

4. Update the maximum length:

   • After ensuring the window is valid, calculate current window size: i - j + 1
   • Update ans with the maximum value seen so far

5. Return the result: After processing all characters, return ans

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

Space Complexity: O(1) since the counter will store at most 3 distinct characters at any time (2 valid + 1 that triggers contraction).

Example Walkthrough

Let's walk through the solution with s = "eceba":

Initial state:

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

Step 1: i=0, c='e'

• Add 'e' to window: cnt = {'e': 1}
• Window is "e" with 1 distinct character (valid)
• Window size = 0 - 0 + 1 = 1
• Update ans = 1

Step 2: i=1, c='c'

• Add 'c' to window: cnt = {'e': 1, 'c': 1}
• Window is "ec" with 2 distinct characters (valid)
• Window size = 1 - 0 + 1 = 2
• Update ans = 2

Step 3: i=2, c='e'

• Add 'e' to window: cnt = {'e': 2, 'c': 1}
• Window is "ece" with 2 distinct characters (valid)
• Window size = 2 - 0 + 1 = 3
• Update ans = 3

Step 4: i=3, c='b'

• Add 'b' to window: cnt = {'e': 2, 'c': 1, 'b': 1}
• Window has 3 distinct characters (invalid!)
• Contract window:
  • Remove s[0]='e': cnt = {'e': 1, 'c': 1, 'b': 1}, move j to 1
  • Still 3 distinct characters, continue contracting
  • Remove s[1]='c': cnt = {'e': 1, 'c': 0, 'b': 1} → remove 'c' from cnt
  • Now cnt = {'e': 1, 'b': 1}, move j to 2
  • Window is "eb" with 2 distinct characters (valid)
• Window size = 3 - 2 + 1 = 2
• ans remains 3

Step 5: i=4, c='a'

• Add 'a' to window: cnt = {'e': 1, 'b': 1, 'a': 1}
• Window has 3 distinct characters (invalid!)
• Contract window:
  • Remove s[2]='e': cnt = {'e': 0, 'b': 1, 'a': 1} → remove 'e' from cnt
  • Now cnt = {'b': 1, 'a': 1}, move j to 3
  • Window is "ba" with 2 distinct characters (valid)
• Window size = 4 - 3 + 1 = 2
• ans remains 3

Final Result: The longest substring with at most 2 distinct characters is "ece" with length 3.

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. The outer loop iterates through each character in the string exactly once with index i, contributing O(n) operations. The inner while loop with pointer j might seem to add complexity, but each character is visited by j at most once throughout the entire execution. This is because j only moves forward and never resets. Therefore, the total number of operations across all iterations is still O(n). The operations inside both loops (Counter updates, dictionary operations, and comparisons) are all O(1) operations.

Space Complexity: O(1)

The space complexity is constant because the Counter dictionary cnt can store at most 3 distinct characters at any point in time (before the while loop reduces it back to 2). Since the problem specifically limits the substring to at most 2 distinct characters, and the size of the character set is fixed (ASCII or Unicode), the space used by the Counter is bounded by a constant and doesn't grow with the input size n. The only other variables used are ans, j, i, and c, which all require constant space.

Common Pitfalls

Pitfall 1: Forgetting to Remove Characters with Zero Count

Issue: A common mistake is decrementing the character count but forgetting to remove the character from the dictionary/counter when its count reaches zero. This leads to incorrect counting of distinct characters.

Incorrect Code:

while len(char_count) > 2:
    char_count[s[left]] -= 1
    # Missing: removal of character when count is 0
    left += 1

Problem: Even though char_count[s[left]] becomes 0, the key still exists in the dictionary, so len(char_count) will count it as a distinct character, causing the algorithm to shrink the window unnecessarily.

Solution: Always remove characters from the dictionary when their count reaches zero:

while len(char_count) > 2:
    char_count[s[left]] -= 1
    if char_count[s[left]] == 0:
        del char_count[s[left]]  # Critical: remove the key entirely
    left += 1

Pitfall 2: Updating Maximum Length at Wrong Time

Issue: Updating the maximum length inside the while loop or before ensuring the window is valid.

Incorrect Code:

for right, char in enumerate(s):
    char_count[char] += 1
    max_length = max(max_length, right - left + 1)  # Wrong: might have >2 distinct chars
  
    while len(char_count) > 2:
        # shrink window

Problem: This updates the maximum length when the window might contain more than 2 distinct characters, leading to incorrect results.

Solution: Only update the maximum length after ensuring the window is valid (contains at most 2 distinct characters):

for right, char in enumerate(s):
    char_count[char] += 1
  
    while len(char_count) > 2:
        # shrink window to make it valid
  
    # Now window is valid, safe to update maximum
    max_length = max(max_length, right - left + 1)

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

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

Incorrect Code:

max_length = max(max_length, right - left)  # Wrong: missing +1

Problem: This underestimates the window size by 1. For example, if left = 0 and right = 2, the actual window contains 3 characters (indices 0, 1, 2), not 2.

Solution: Always use right - left + 1 for inclusive window size:

max_length = max(max_length, right - left + 1)  # Correct: includes both endpoints

Pitfall 4: Using Wrong Data Structure

Issue: Using a set to track distinct characters instead of a counter/dictionary.

Incorrect Approach:

distinct_chars = set()
for right, char in enumerate(s):
    distinct_chars.add(char)
    # How do we know when to remove a character?

Problem: A set only tracks presence, not frequency. When shrinking the window, you can't determine when a character should be removed from the set (when its last occurrence leaves the window).

Solution: Use a Counter or dictionary to track frequencies, allowing proper removal when count reaches zero:

char_count = Counter()  # or char_count = {}
# This allows tracking when characters completely leave the window