Domain 2MediumCORE

Longest Substring with At Most Two Distinct Characters

We are given a string s and need to find the maximum length of any contiguous substring that contains no more than two unique characters (e.g., 'aabb' is valid, but 'abc' is not).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table#Two Pointers#String#Sliding Window

159. Longest Substring with At Most Two Distinct Characters

Model: qwen3.5:9b
Topics: Hash Table,Two Pointers,String,Sliding Window
FAANG asked: 1
Acceptance rate: 50.7%


Problem Breakdown

We are given a string s and need to find the maximum length of any contiguous substring that contains no more than two unique characters (e.g., “aabb” is valid, but “abc” is not).

Inputs: A single string s. Outputs: An integer representing the max length. Constraints: Length up to 10410^4, English letters only.

Edge Cases/Tricky Parts:

  • Empty String: Though constraints say ≥1\ge 1, logic should handle it gracefully (return 0).
  • All Same Characters: The window expands until the end of string; length is len(s).
  • More than Two Distinct Chars: This forces us to shrink our window from the left. We must ensure we don’t lose track of which character caused the violation when shrinking.

Intuition

A brute-force approach would iterate through every possible substring, count distinct characters for each (O(N3)O(N^3) or O(N2)O(N^2)), and take the max length. This is too slow given N=104N=10^4.

The property we are optimizing (longest valid window) suggests a Sliding Window technique with two pointers (left and right). As we expand the right pointer, if our condition (at most 2 distinct chars) breaks, we must shrink from the left until it’s satisfied again. Since characters only get added or removed once as pointers move forward, this is linear time.

Approach

  1. Initialize two pointers: left at start of string, and iterate right through the string.
  2. Maintain a frequency map (count) for characters currently inside our window [left, right].
  3. In each iteration (expanding right):
    • Add current character to count.
  4. Check validity: If number of keys in count exceeds 2:
    • We must shrink the window from the left until we have ≤\le 2 distinct characters again.
    • Remove s[left] from our map (decrement count).
    • If frequency drops to zero, remove key entirely so length of keys reflects unique chars accurately.
    • Increment left.
  5. Track the maximum window size (right - left + 1) at every valid step.

Complexity Analysis

  • Time: O(N)O(N) where NN is string length. Both pointers traverse the string once; dictionary operations are amortized O(1)O(1).
  • Space: O(K)O(K) where KK is alphabet size (26 for English letters). Since we only store at most 3 characters in our map during execution, this effectively acts as constant space relative to input constraints.

Solution

def lengthOfLongestSubstringTwoDistinct(s: str) -> int:
    # Frequency map of current window
    char_count = {}
    
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        c_right = s[right]
        
        # Add new character to the window
        if c_right not in char_count:
            char_count[c_right] = 1
        else:
            char_count[c_right] += 1
            
        # If we have more than 2 distinct characters, shrink from left
        while len(char_count) > 2:
            c_left = s[left]
            
            # Decrement count for character leaving the window
            if char_count[c_left] == 1:
                del char_count[c_left]
            else:
                char_count[c_left] -= 1
            
            left += 1
        
        # Update max length found so far
        current_len = right - left + 1
        if current_len > max_len:
            max_len = current_len
            
    return max_len

Edge Cases Handled

  • Single Character String: Loop runs once, max_len becomes 1. Correct.
  • String with <2 Distinct Chars (e.g., “aaaa”): Window expands to full length; condition never triggers shrinkage. Returns NN. Correct.
  • Window Shrinking Logic: When removing characters from the left, we explicitly delete keys when count hits 0. This ensures len(char_count) accurately reflects unique distinct characters in the current window before calculating max_len.