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.

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

python

▶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

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.

06

Complexity

Time

O(n)

Space

O(k)

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