Prerequisites
Before attempting this problem, you should be comfortable with:
- Sliding Window Technique - Essential for efficiently finding the longest valid substring without rechecking overlapping portions
- Hash Map / Dictionary - Used to track character frequencies within the current window and count distinct characters
- Two Pointers - The sliding window is implemented using left and right pointers to define window boundaries
1. Brute Force
Intuition
The most direct approach is to examine every possible substring and check if it contains at most two distinct characters. For each starting position, we extend the substring character by character, tracking the distinct characters seen. Once we see a third distinct character, we stop and record the maximum valid length found.
Algorithm
- Initialize
res = 0to store the maximum length. - For each starting index
ifrom0ton-1:- Create a set
seento track distinct characters. - Initialize
curLen = 0. - For each ending index
jfromiton-1:- Add
s[j]to the set. - If the set size exceeds
2, break out of the inner loop. - Otherwise, increment
curLen.
- Add
- Update
res = max(res, curLen).
- Create a set
- Return
res.
Time & Space Complexity
- Time complexity:
- Space complexity: since we have at most different characters.
2. Sliding Window
Intuition
We maintain a window that always contains at most two distinct characters. As we expand the window to the right, we track character frequencies in a hash map. When adding a new character causes us to have more than two distinct characters, we shrink the window from the left until we're back to two or fewer distinct characters.
Algorithm
- Initialize
res = 0,j = 0(left pointer), and a hash mapseenfor character counts. - For each
i(right pointer) from0ton-1:- Increment the count of
s[i]in the map. - While the map contains more than
2distinct characters:- Decrement the count of
s[j]. - If the count reaches
0, removes[j]from the map. - Increment
j.
- Decrement the count of
- Update
res = max(res, i - j + 1).
- Increment the count of
- Return
res.
class Solution:
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
res, n = 0, len(s)
seen = defaultdict(int)
j = 0
for i in range(n):
seen[s[i]] += 1
while len(seen) > 2:
seen[s[j]] -= 1
if seen[s[j]] == 0:
seen.pop(s[j])
j += 1
res = max(res, i - j + 1)
return resTime & Space Complexity
- Time complexity:
- Space complexity: since we have at most different characters.
3. Sliding Window (Optimal)
Intuition
We can further optimize by observing that we only care about the maximum window size. Instead of tracking the actual maximum during iteration, we maintain a window that never shrinks by more than one element at a time. When we have too many distinct characters, we shift the entire window right by one. The final window size represents the longest valid substring.
Algorithm
- Initialize
j = 0(left pointer) and a hash mapcountfor character frequencies. - For each
ifrom0ton-1:- Increment the count of
s[i]. - If more than
2distinct characters:- Decrement the count of
s[j]. - If count becomes
0, remove from map. - Increment
j.
- Decrement the count of
- Increment the count of
- Return
i - j + 1(orn - jafter the loop).
Time & Space Complexity
- Time complexity:
- Space complexity: since we have at most different characters.
Common Pitfalls
Forgetting to Remove Characters with Zero Count
When shrinking the window from the left, you must remove characters from the hash map when their count drops to zero. If you only decrement the count without removing the entry, the map size will incorrectly reflect more distinct characters than actually exist in the window, causing premature window shrinking.
Confusing "At Most Two" with "Exactly Two"
The problem asks for substrings with at most two distinct characters, not exactly two. This means substrings with zero or one distinct character are also valid. Ensure your solution counts these cases correctly and does not skip windows with fewer than two distinct characters.
Incorrect Window Boundary Updates
A common mistake is updating the result before fully adjusting the window to be valid. Always ensure the window contains at most two distinct characters before calculating and updating the maximum length. Update the result after the while loop that shrinks the window, not before.