LeetCode 159 – Longest Substring with At Most Two Distinct Characters

This is the sliding window at its most reusable: a window that grows greedily and shrinks only when a single condition is violated. It is Minimum Window Substring's easier sibling, and unlike that one it generalises to "at most k" by changing a literal 2.

The problem

Given a string, return the length of the longest substring containing at most two distinct characters.

"eceba"    -> 3      "ece"
"ccaabbb"  -> 5      "aabbb"
"a"        -> 1
""         -> 0
"abcabcabc"-> 2      no three consecutive characters share only two letters
"aaaa"     -> 4      one distinct character is "at most two"

At most, not exactly. "aaaa" qualifies with one distinct character — misreading that costs you the whole problem, and it is the sort of thing worth restating back to the interviewer.

Grow, then shrink

Extend the right edge one character at a time. If the window now holds three distinct characters, pull the left edge in until it holds two again. Record the size after every step.

"ccaabbb"

[cc]          {c:2}          size 2
[ccaa]        {c:2, a:2}     size 4
[ccaab]       {c,a,b}  -- three! shrink from the left
  [caab]      still three
   [aab]      {a:2, b:1}     size 3
   [aabb]     size 4
   [aabbb]    size 5   <- best

Both pointers only ever move right, so the whole thing is O(n) despite the nested loop — the same amortised argument as problem 76 and Valid Palindrome. Each character is added once and removed at most once.

The counter that must be removed, not just decremented

The window's validity is "how many distinct characters do I have", which is the size of the map. So when a character's count reaches zero it has to be deleted, not left sitting at 0:

counts["c"] -= 1
if counts["c"] == 0: del counts["c"]      <- without this, len(counts) never shrinks

Leave the zero entry in and len(counts) counts characters that are no longer in the window, the shrink loop never terminates its condition, and the answer collapses. This is the one bug the problem has, and it is invisible on inputs where every character reappears.

The while — not if — also matters. Removing one character may not be enough if the window is long and the leftmost character is repeated: "aabbc" needs both as gone before the window is valid again.

Java

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        Map<Character, Integer> counts = new HashMap<>();
        int best = 0, left = 0;

        for (int right = 0; right < s.length(); right++) {
            counts.merge(s.charAt(right), 1, Integer::sum);

            // WHILE, not if: one removal may not be enough.
            while (counts.size() > 2) {
                char leaving = s.charAt(left++);
                int remaining = counts.merge(leaving, -1, Integer::sum);

                if (remaining == 0) {
                    counts.remove(leaving);   // or size() never shrinks
                }
            }

            best = Math.max(best, right - left + 1);
        }

        return best;
    }
}

counts.size() is the number of distinct characters, which is the whole validity test — no separate counter is needed here, unlike problem 76, where the condition involved multiplicities and needed its own integer.

best is updated after the shrink, when the window is guaranteed valid. Updating before would record an invalid three-character window.

merge handles both the insert and the increment, and returns the new value — which is exactly what the removal check needs. It is worth knowing over the getOrDefault/put pair.

Python

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        counts: dict[str, int] = {}
        best = left = 0

        for right, c in enumerate(s):
            counts[c] = counts.get(c, 0) + 1

            while len(counts) > 2:
                leaving = s[left]
                counts[leaving] -= 1
                if counts[leaving] == 0:
                    del counts[leaving]       # len() must reflect the window
                left += 1

            best = max(best, right - left + 1)

        return best

Use a plain dict rather than collections.Counter here. Counter does not drop keys when a count hits zero, so len() would keep counting characters that have left the window — the exact bug above, delivered by the convenience class.

The last-seen-index variant

There is a neater formulation for the specific case of two characters: keep a map from character to its last index, capped at two entries. When a third arrives, the character to evict is the one with the smallest last index, and the left edge jumps straight past it:

lastSeen = {char -> most recent index}
on a third character:
    evict = the char with the smallest last index
    left  = lastSeen[evict] + 1
    remove evict

The left pointer jumps instead of stepping, so there is no inner loop at all. It is elegant and it stops scaling: finding the minimum among k entries is fine for two and becomes a priority queue for large k. Mention it, then keep the counting version.

Complexity

The map never holds more than three entries — two valid ones plus the intruder being evicted — so the space is constant regardless of alphabet size. That is worth stating precisely; "O(k)" is the honest general answer and k is 2 here.

The family

The first four are one algorithm. Problem 76 is the odd one out because it minimises rather than maximises, which flips where the recording happens: here you record after shrinking to valid, there you record while valid and keep shrinking. Knowing which way round that goes is most of what distinguishes the two shapes.

What the interviewer is checking

• "At most" two, so one distinct character qualifies.
• Deleting the map entry at zero, not merely decrementing.
• while rather than if on the shrink.
• Recording the best after shrinking, when the window is valid.
• That both pointers move forward only, hence O(n).
• Empty string, single character, all-identical string.
• That it generalises to k by changing one literal.