Longest Substring with At Most K Distinct Characters

Longest Substring with At Most K Distinct Characters is a classic sliding window problem. It teaches the core window move: let the right edge grow greedily, and only pull the left edge in when the window breaks a rule.

The slow way first

The brute-force idea: try every starting index, extend to every ending index, and count distinct characters each time. That is O(n²) substrings, and counting distinct characters inside each makes it even worse.

The question to ask: as I extend a window to the right, do I ever need to back up the left edge? No — once a window starting at lo becomes invalid, every shorter hi would still have been valid, so lo only ever moves forward. That monotonic left edge is exactly what makes a single pass possible.

The idea: one window, two edges

Keep a window [lo, hi] and a count map of how many times each character appears inside it. Move hi forward one character at a time, adding it to the map. Whenever the map holds more than k distinct keys, shrink from the left: remove s[lo], drop it from the map if its count hits zero, and advance lo. After each valid step, record the window length.

The number of distinct characters is just len(count). We only delete a key when its count reaches zero, so the map size always equals the true distinct count of the current window.

Walk through it

Step through the animation. The hi pointer scans left to right, adding each character to count. When b arrives the window has three distinct characters, so lo advances until the window is valid again. The best length we ever recorded was 3, from the window "ece".

Pseudocode

count = empty map        # char -> how many times it appears in the window
lo = 0
best = 0
for hi from 0 to len(s) - 1:
    add s[hi] to count
    while count has more than k distinct keys:
        remove s[lo] from count (delete the key if its count hits 0)
        lo = lo + 1
    best = max(best, hi - lo + 1)
return best

The Python solution

def longest_k_distinct(s, k):
    count = {}
    lo = best = 0
    for hi, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        while len(count) > k:
            left = s[lo]
            count[left] -= 1
            if count[left] == 0:
                del count[left]
            lo += 1
        best = max(best, hi - lo + 1)
    return best

• count maps each character to how many times it appears in the current window.
• enumerate gives us the right edge hi and its character ch as we extend.
• After adding ch, line 6 checks the invariant: while there are more than k distinct keys, the window is invalid.
• To shrink, we decrement the leftmost character; when its count drops to 0 we del the key so len(count) stays exactly the distinct count.
• best = max(best, hi - lo + 1) records the window length after it is guaranteed valid.

Complexity

Although there is a while loop inside the for, each character is added once and removed once across the whole run, so the total work is O(n). The map never holds more than k + 1 keys, so space is O(k).

When this pattern shows up

Practice