Longest Substring with At Most Two Distinct Characters

How it works

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.

Steps

1. Initialize j = 0 (left pointer) and a hash map count for character frequencies.
2. For each i from 0 to n-1:
   • Increment the count of s[i].
   • If more than 2 distinct characters:
     • Decrement the count of s[j].
     • If count becomes 0, remove from map.
     • Increment j.
3. Return i - j + 1 (or n - j after the loop).

Complexity

• Time complexity: O(n)
• Space complexity: O(1) since we have at most 52 different characters.

Things to watch for

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.

from collections import defaultdict

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        n = len(s)
        count = defaultdict(int)
        j = 0

        for i in range(n):
            count[s[i]] += 1
            if len(count) > 2:
                count[s[j]] -= 1
                if count[s[j]] == 0:
                    count.pop(s[j])
                j += 1
        return i - j + 1

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int n = s.size();
        unordered_map<char, int> count;
        int j = 0, i = 0;
        for (i = 0; i < n; i++) {
            count[s[i]]++;
            if (count.size() > 2) {
                count[s[j]]--;
                if (count[s[j]] == 0) count.erase(s[j]);
                j++;
            }
        }
        return i - j;
    }
};