← Visualizers
Sliding Window · variable window, sub-variant B — maximise LeetCode 340

Longest Substring with At Most K Distinct Characters / visualized

Same machine as every other maximise window, but the state carried along is no longer an integer — it is a char → count map, and the invariant is map.size() ≤ k. r always advances and bumps a count. While the window is invalid (size > k) the left character is decremented, and when its count reaches zero the key must be removed from the map. That one line is the entire difficulty of this problem: map.size() counts keys, not positive counts, so a key left behind at zero means the size never shrinks, the loop never exits, and the window eats the string. best is recorded after the shrink loop — sub-variant B.

Execution

idle
s  ·  teal cells are inside the window
map  ·  char → count inside the window
Press Run to begin.
The classic bug: decrementing to zero but never calling map.remove(c). size() counts keys, so it stays above k forever and the shrink loop cannot terminate. Watch for the amber “count 0” chip — that is the instant the removal has to fire.
0 / 0
Speed

Java · running line

inside the window / live key count incremented count decremented count hit 0 — remove now longest window recorded key deleted / left behind
O(n) time · O(k) space  ·  every index is inserted once and erased once, and the map holds at most k+1 keys. Sub-variant B: record best after the shrink loop. map.size() is the invariant — keep it honest by deleting keys at zero.