STEP 10 · SLIDING WINDOW · SLIDING WINDOW · MEDIUM

Longest Substring with At Most K Distinct Characters

WHAT IT SAYS

Given a string and a number k, find the length of the longest stretch containing at most k distinct characters.

WHAT IT'S REALLY ASKING

"Distinct-count is a ratchet: reaching right can only add a new character, never retire one, and pulling the left edge in can only retire one, never add. So a stretch that has already blown past k is finished for good — and the only real subtlety left is that a character doesn't leave the window when you drop *a* copy of it, it leaves when you drop its *last* copy."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Fix a start, extend until the k+1-th character shows up

O(n²) time, O(k) space

For each start i, walk right maintaining a map of character counts, stop as soon as the map holds k + 1 keys, and record how far you got. Restart from i + 1 with a fresh map. Every candidate stretch is measured, so it's correct.

WHERE THE WORK IS WASTED — Every restart rebuilds a map that differed from the previous one by a single decrement. The pass from i counted the characters of s[i+1..r] on its way out; the pass from i + 1 counts those same characters from an empty map, and then dies on the same intruding character at (usually) the same index r. Worse, you throw away a fact you'd already proved: every start from i up to the point where that intruder's blocker clears is guaranteed to die at r too, and brute force re-derives each of those deaths with a full scan.

KEY OBSERVATION — THE UNLOCKlink

Distinct-count only climbs right and only falls left.

Push the right edge out by one: the character either was already in the window (count unchanged) or wasn't (count up by one). It cannot go down. So if [i..r] already holds k + 1 distinct characters, then [i..r'] for every r' beyond r holds at least that many — start i isn't temporarily invalid, it is dead for the rest of the scan, and every start before it is dead with it. Run the same argument leftward: pulling the left edge in removes an occurrence, so the distinct-count either stays put or drops by one. It never rises. That makes validity hereditary — if [l..r+1] is under budget, then [l..r] was too — and therefore the leftmost surviving start for r + 1 can never lie to the left of the leftmost surviving start for r. The left edge is monotone: it advances or it waits, but it never rewinds. One pass with two pointers, and the map is the only thing you carry. But note what the map has to hold. In the no-repeats version of this problem you could remember each character's last position and *jump* the left edge in one hop. Here you can't: dropping one 'a' from a window holding three of them changes nothing about the distinct-count, because 'a' is still in there. A character leaves only when its last copy leaves — so the map counts occurrences, and the left edge crawls.

Right adds, left crawls until a character finally dies

O(n) time, O(k) space

Advance the right edge, incrementing that character's count and bumping the distinct-count when its count rises from zero. While the distinct-count exceeds k, walk the left edge forward decrementing counts, and drop the distinct-count only at the moment some count actually hits zero. The crawl looks like a nested loop, but each index is decremented at most once across the whole run, so the total work is 2n.

The window that only ever grows

O(n) time, O(k) space, one pointer move per index

Since only the maximum length matters, an over-budget window never has to shrink — it only has to stop growing. Replace the while with a single if: when the distinct-count exceeds k, slide the left edge forward by exactly one, so the window drifts at its current width instead of collapsing. It can only widen again when a genuinely valid window of the next width appears, so the final width is the answer with no max-tracking at all.

WHAT YOU TRADED — You pay O(k) memory for the linear scan, but the real price is a precondition you never see: the window only works because the constraint is monotone in width, so the left edge is safe never to rewind. And the shape of the map is dictated by the problem, not by taste — an equality-style constraint on a *set* lets you jump the left edge with last-seen positions, while a constraint on a *multiset* forces you to count occurrences and crawl.

WATCH THE IDEA RUN

width 0

best 0

distinct / 2 0

Budget: at most 2 distinct characters. Watch the left edge — and watch what happens when it drops a character that has a twin still inside.

step 1 / 23

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Ratchet Window

YOU'LL SEE IT AGAIN WHEN

You want the longest contiguous stretch under a budget on some quantity that only rises as the window widens and only falls as it narrows — never the other way.
When a window busts, you can name the element that busted it, so you know which starts died with it rather than merely that some did.
The quantity is a property of the window's contents as a multiset (how many distinct, how many of a kind), so it updates in O(1) as one element enters or leaves.
The same problem statement with k = 1 or k = 2 is a well-known easy special case — a hint that k is a budget, not a structural constant.

SAME BLUEPRINT, DIFFERENT PROBLEM

Fruit Into BasketsLongest Substring Without Repeating CharactersMax Consecutive Ones IIISubarrays with K Different Integers

The bar isn't "solved it once." It's "could rebuild it from the observation."