Longest Substring with At Most K Distinct Characters
Return the length of the longest substring containing at most k distinct characters.
- 1 <= |s| <= 10⁵
- 0 <= k <= 26
- s consists of lowercase English letters
- Return 0 when k is 0
Intuition
Longest substring with at most k distinct characters finds the longest substring containing no more than k unique characters. It is the general form of Fruit Into Baskets, which fixes k = 2.
The window is variable-length, and the invariant is direct:
- Extend the right edge freely, and whenever the window holds more than k distinct characters, shrink from the left until it holds k again.
A hash map from character to count tracks the window's contents, and the map's size is the number of distinct characters — which is the quantity being constrained.
The detail that breaks implementations is when to remove a character from the map. Delete it only when its count reaches zero, not on the first decrement:
In a window like "aba", removing the first a leaves another a behind. Deleting the key immediately would report two distinct characters as one and admit windows that violate the constraint.
The maximum length must be recorded after the shrink completes, when the window is valid again. Measuring during the shrink records an oversized invalid window.
The left pointer only ever moves forward, so although the code has a nested loop, each character enters and leaves the window at most once and the scan is linear.
Edge cases resolve without special handling: k = 0 yields 0, since no character may appear, and a string with fewer than k distinct characters is entirely valid and returns its full length.
The canonical k-distinct window, and the parent of several disguised problems (fruit baskets is this with k = 2). A frequency map tracks the window's contents; len(freq) is the validity test; deleting keys at zero is what keeps that test honest.
Approach
Before reading on: price up what counting everything costs here, then ask what makes a window invalid, and which pointer should move when it is. Aim for O(n) time and O(k) space.
Track distinct characters with a map
A character-to-count map describes the window, and its size is the number of distinct characters — exactly the quantity being constrained.
Extend the right edge
Move right one character at a time, incrementing its count. The window grows until the distinct count exceeds k.
Shrink when over the limit
While the map holds more than k keys, decrement the leftmost character and advance the left pointer until the constraint holds again.
Remove a key only at zero
Delete a character from the map only when its count reaches 0. In "aba", removing the first a leaves another behind — deleting early miscounts the distinct total.
Record after shrinking
Update the maximum once the window is valid again. Measuring mid-shrink records an oversized window that violates the constraint.
Handle the boundary values
k = 0 returns 0, since no character may appear. A string with fewer than k distinct characters is fully valid and returns its whole length.
Cost of the scan
Each character enters and leaves the window once, giving O(n) time, with O(k) space for the map.
Solution & live demo
Common pitfalls
Keeping keys after their count reaches zero
freq[out] -= 1 left += 1
freq[out] -= 1
if freq[out] == 0:
del freq[out]
left += 1len(freq) counts keys, not positive counts. A key stranded at zero makes the window look more diverse than it is, so it shrinks past the real answer.
Testing distinctness against the window length
while right - left + 1 > k:
while len(freq) > k:
The constraint bounds distinct characters, not the substring's length. Bounding the length caps every answer at k and ignores repeats entirely.
Not handling k = 0
# assume k >= 1
while len(freq) > k: # naturally empties the window when k == 0
With k = 0 the only valid substring is empty. The while loop handles it correctly by shrinking left up to right + 1; an if-based shrink would leave a one-character window and return 1.
Edge cases
No characters are allowed, so the answer is 0.
The whole string qualifies and the answer is len(s).
len(freq) overstates the distinct count and the window collapses — the most common failure here.
The loop never runs and 0 is returned.