Facebook Pixel

159. Longest Substring with At Most Two Distinct Characters 🔒

MediumHash TableStringSliding Window
Leetcode Link

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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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).

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

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

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
Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More