159. Longest Substring with At Most Two Distinct Characters 🔒
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) andi
(right boundary, implicit in the enumeration)
Algorithm Steps:
-
Initialize variables:
cnt = Counter()
- tracks character frequencies in current windowans = 0
- stores the maximum length foundj = 0
- left pointer of the sliding window
-
Expand the window: Iterate through each character in the string using
enumerate(s)
:- Add the current character
c
to the window by incrementingcnt[c]
- The right boundary of the window is at position
i
- Add the current character
-
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
- Decrease the count of the leftmost character
-
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
- After ensuring the window is valid, calculate current window size:
-
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).
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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)
- Remove s[0]='e':
- 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)
- Remove s[2]='e':
- 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
1from collections import Counter
2
3class Solution:
4 def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
5 # Dictionary to track character frequencies in current window
6 char_count = Counter()
7
8 # Initialize result and left pointer of sliding window
9 max_length = 0
10 left = 0
11
12 # Iterate through string with right pointer
13 for right, char in enumerate(s):
14 # Add current character to window
15 char_count[char] += 1
16
17 # Shrink window from left while we have more than 2 distinct characters
18 while len(char_count) > 2:
19 # Decrease count of leftmost character
20 char_count[s[left]] -= 1
21
22 # Remove character from dictionary if count reaches 0
23 if char_count[s[left]] == 0:
24 del char_count[s[left]]
25
26 # Move left pointer forward
27 left += 1
28
29 # Update maximum length found so far
30 # Current window length is right - left + 1
31 max_length = max(max_length, right - left + 1)
32
33 return max_length
34
1class Solution {
2 public int lengthOfLongestSubstringTwoDistinct(String s) {
3 // HashMap to store character frequencies in the current window
4 Map<Character, Integer> charFrequencyMap = new HashMap<>();
5 int stringLength = s.length();
6 int maxLength = 0;
7
8 // Use sliding window with two pointers: left and right
9 int left = 0;
10 for (int right = 0; right < stringLength; right++) {
11 // Add current character to the window
12 char currentChar = s.charAt(right);
13 charFrequencyMap.put(currentChar, charFrequencyMap.getOrDefault(currentChar, 0) + 1);
14
15 // Shrink window from left while we have more than 2 distinct characters
16 while (charFrequencyMap.size() > 2) {
17 char leftChar = s.charAt(left);
18 left++;
19
20 // Decrease frequency of the character being removed from window
21 charFrequencyMap.put(leftChar, charFrequencyMap.get(leftChar) - 1);
22
23 // Remove character from map if its frequency becomes 0
24 if (charFrequencyMap.get(leftChar) == 0) {
25 charFrequencyMap.remove(leftChar);
26 }
27 }
28
29 // Update maximum length found so far
30 // Window size is (right - left + 1)
31 maxLength = Math.max(maxLength, right - left + 1);
32 }
33
34 return maxLength;
35 }
36}
37
1class Solution {
2public:
3 int lengthOfLongestSubstringTwoDistinct(string s) {
4 // Hash map to store character frequencies in the current window
5 unordered_map<char, int> charFrequency;
6
7 int n = s.size();
8 int maxLength = 0;
9 int left = 0; // Left pointer of the sliding window
10
11 // Right pointer traverses the string
12 for (int right = 0; right < n; ++right) {
13 // Add current character to the window
14 charFrequency[s[right]]++;
15
16 // Shrink window if we have more than 2 distinct characters
17 while (charFrequency.size() > 2) {
18 // Decrease frequency of the leftmost character
19 charFrequency[s[left]]--;
20
21 // Remove character from map if its frequency becomes 0
22 if (charFrequency[s[left]] == 0) {
23 charFrequency.erase(s[left]);
24 }
25
26 // Move left pointer to shrink the window
27 ++left;
28 }
29
30 // Update maximum length found so far
31 maxLength = max(maxLength, right - left + 1);
32 }
33
34 return maxLength;
35 }
36};
37
1function lengthOfLongestSubstringTwoDistinct(s: string): number {
2 // Hash map to store character frequencies in the current window
3 const charFrequency: Map<string, number> = new Map();
4
5 const n: number = s.length;
6 let maxLength: number = 0;
7 let left: number = 0; // Left pointer of the sliding window
8
9 // Right pointer traverses the string
10 for (let right = 0; right < n; right++) {
11 // Add current character to the window and update its frequency
12 const currentChar: string = s[right];
13 charFrequency.set(currentChar, (charFrequency.get(currentChar) || 0) + 1);
14
15 // Shrink window if we have more than 2 distinct characters
16 while (charFrequency.size > 2) {
17 // Get the leftmost character
18 const leftChar: string = s[left];
19
20 // Decrease frequency of the leftmost character
21 const leftCharFreq: number = charFrequency.get(leftChar)! - 1;
22
23 // Remove character from map if its frequency becomes 0
24 if (leftCharFreq === 0) {
25 charFrequency.delete(leftChar);
26 } else {
27 charFrequency.set(leftChar, leftCharFreq);
28 }
29
30 // Move left pointer to shrink the window
31 left++;
32 }
33
34 // Update maximum length found so far
35 maxLength = Math.max(maxLength, right - left + 1);
36 }
37
38 return maxLength;
39}
40
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
How many ways can you arrange the three letters A, B and C?
Recommended Readings
https assets algo monster cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in the window The window
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!