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 , English letters only.
Edge Cases/Tricky Parts:
- Empty String: Though constraints say , 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 ( or ), and take the max length. This is too slow given .
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
- Initialize two pointers:
leftat start of string, and iteraterightthrough the string. - Maintain a frequency map (
count) for characters currently inside our window[left, right]. - In each iteration (expanding
right):- Add current character to
count.
- Add current character to
- Check validity: If number of keys in
countexceeds 2:- We must shrink the window from the left until we have 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.
- Track the maximum window size (
right - left + 1) at every valid step.
Complexity Analysis
- Time: where is string length. Both pointers traverse the string once; dictionary operations are amortized .
- Space: where 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_lenbecomes 1. Correct. - String with <2 Distinct Chars (e.g., “aaaa”): Window expands to full length; condition never triggers shrinkage. Returns . 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.