LeetCode #340 Medium

Longest Substring with At Most K Distinct Characters

Return the length of the longest substring containing at most k distinct characters.

sliding-windowhashmapstrings

02

Intuition

Same window template as the binary-flips problem, with the constraint upgraded from a counter to a frequency map. The window is legal while the map holds at most k keys; when a k+1th key appears, shrink from the left and delete keys as their counts hit zero. The trap is skipping the delete: if a count hits zero but the key stays in freq, len(freq) keeps counting a character that is no longer in the window, so the shrink condition never clears and the window gets squeezed down to nothing.

How to spot this pattern

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.

03

Approach

1

Define the constraint as map size

Keep a dictionary from character to count for the current window. The number of distinct characters is exactly len(freq), so the legality test is len(freq) <= k. The brute force enumerates all O(n^2) substrings and builds a set for each — the window reuses that work instead.

2

Grow right and add to the map

For each right, do freq[s[right]] += 1. A brand-new character raises the distinct count by one, which is the only way the window can become illegal — so the shrink check only needs to run after an insert.

3

Shrink and delete zeroed keys

While len(freq) > k, decrement freq[s[left]] and advance left, and delete the key when its count reaches zero. Forgetting the delete is the standard bug: the map keeps a stale key, len(freq) never drops, and the loop shrinks the window to nothing. After shrinking, update the best length. O(n) time, O(k) space for the map.

04

Solution & live demo

▶1class Solution:
▶2    def lengthOfLongestSubstringKDistinct(self, s, k):
▶3        freq = {}
▶4        left = best = 0
▶5        for right, ch in enumerate(s):
▶6            freq[ch] = freq.get(ch, 0) + 1
▶7            while len(freq) > k:
▶8                out = s[left]
▶9                freq[out] -= 1
▶10                if freq[out] == 0:
▶11                    del freq[out]
▶12                left += 1
▶13            best = max(best, right - left + 1)
▶14        return best

05

Common pitfalls

Keeping keys after their count reaches zero

✗ Wrong

freq[out] -= 1
left += 1

✓ Right

freq[out] -= 1
if freq[out] == 0:
    del freq[out]
left += 1

len(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

✗ Wrong

while right - left + 1 > k:

✓ Right

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

✗ Wrong

# assume k >= 1

✓ Right

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.

06

Edge cases

k = 0

No characters are allowed, so the answer is 0.

k >= number of distinct characters

The whole string qualifies and the answer is len(s).

Forgetting to delete zero-count keys

len(freq) overstates the distinct count and the window collapses — the most common failure here.

Empty string

The loop never runs and 0 is returned.

07

Complexity

Time

O(n)

Space

O(k)

The map never holds more than k+1 keys at any moment.