At Most K Distinct

What is this?

You are walking a street of food stalls with two baskets, picking up fruit as you go, and you may only ever carry two kinds. You never skip a stall and never walk backwards — when a third kind appears, you drop fruit from the back of your haul until only two kinds remain. The longest unbroken stretch you managed is the answer.

That is the entire technique, and it is worth noticing that the rule is about the number of kinds, not the amount. You can carry twenty apples; you cannot carry three kinds.

💡 Fun fact: this template is the answer to a startling number of differently-worded problems — Longest Substring Without Repeating Characters is k = 1 per character, Fruit Into Baskets is k = 2 wearing a costume, and Subarrays With K Different Integers is this function called twice and subtracted. When you meet a new window problem, the useful first question is not "how do I solve this" but "is this at-most-k in disguise?"

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: grow the window every step, shrink it while it holds more than k distinct values, and record the length whenever it is valid. The distinct count is len(map), which is only true if you delete keys the moment their count reaches zero.

1. The template

from collections import defaultdict

def longest_at_most_k(s: str, k: int) -> int:
    count = defaultdict(int)
    left = best = 0
    for right, ch in enumerate(s):
        count[ch] += 1
        while len(count) > k:            # while, not if
            out = s[left]
            count[out] -= 1
            if count[out] == 0:
                del count[out]           # or len(count) lies
            left += 1
        best = max(best, right - left + 1)
    return best

Six lines, two of which are the whole difficulty:

while, not if. With this particular invariant a single arrival adds at most one new key, so one shrink step happens to suffice — but write while anyway. The moment the condition becomes "sum ≤ target" or "at most k odd numbers", one arrival can break it by more than one element, and an if fails silently on inputs you will not think to test.

Delete at zero. len(count) is the distinct-value count only if exhausted keys are removed. Leave a key sitting at zero and the window believes it is still carrying a fruit it dropped, so it shrinks further than it should and every answer comes back short.

2. Why it is O(n) despite the nested loop

left never decreases and never passes right. Across the entire run it advances at most n times in total, so the inner while performs at most n iterations summed over all outer steps — not per step. Each element is added exactly once and removed at most once.

This amortisation argument is what interviewers listen for. "It's a sliding window so it's O(n)" is a memorised phrase; "both pointers are monotonic, so each element enters and leaves once" is an explanation.

3. A 30-second worked example

s = "eceba", k = 2.

right ch  map after add       action                    window   best
 0    e   {e:1}               valid                     "e"        1
 1    c   {e:1,c:1}           valid                     "ec"       2
 2    e   {e:2,c:1}           valid                     "ece"      3
 3    b   {e:2,c:1,b:1}       3 > 2 → shrink:
                              drop 'e' → {e:1,c:1,b:1}   still 3
                              drop 'c' → {e:1,b:1}       valid     "eb"       3
 4    a   {e:1,b:1,a:1}       3 > 2 → shrink:
                              drop 'e' → {b:1,a:1}       valid     "ba"       3
                                                           answer = 3

Two things to notice. The shrink at right = 3 ran twice, because dropping 'e' left three kinds still present — the clearest possible argument for while over if. And 'c' was deleted from the map at that moment, which is what let len(count) fall back to 2.

4. Where you'll actually meet this

• Session and cohort analysis. "Longest run of events involving at most k distinct users/devices" is this loop over a log.
• Cache and working-set sizing. The longest stretch of a trace touching at most k distinct pages is exactly the question that motivates LRU cache capacity choices.
• Bandwidth and connection limits. Longest period during which a client contacted no more than k distinct endpoints — a real anomaly-detection signal.
• Text and DNA analysis. Longest substring over a restricted alphabet, used in read filtering and low-complexity region detection.
• Inventory constraints. The literal fruit-baskets framing: how much can you collect from consecutive stalls with limited container types.

5. Problems in this chapter

▶ Longest Substring with At Most Two Distinct Characters

The template with k hard-coded to 2. Worth solving first precisely because the small k makes it easy to trace by hand and see the deletion matter.
Pattern: grow-and-shrink with a count map. Target: O(n) time, O(1) space (at most 3 keys live).

▶ Longest Substring with At Most K Distinct Characters

The same function with k as a parameter. The generalisation is free — which is the point — and it is the version worth memorising, since "exactly k" and its relatives are built from it.
Pattern: grow-and-shrink with a count map. Target: O(n) time, O(k) space.

6. Common pitfalls 🚫

• if instead of while. Correct for this invariant, wrong the moment the invariant changes — and the habit is what carries you between problems.
• Not deleting zero-count keys. The single most common bug here; the code runs, returns plausible numbers, and is wrong on inputs where a character leaves and returns.
• Using sum(count.values()) to test distinctness. That is the window's length, not its variety.
• Recording the answer inside the shrink loop. Measure only after the window is valid again.
• Returning the substring when the length was asked for (or vice versa) — check which, and remember that reconstructing the substring needs you to store left at the best moment.
• Assuming k is sane. k = 0 should return 0, not loop forever; a one-line guard costs nothing.
• Reaching for this when the constraint is not monotonic. Growing the window must only ever increase the distinct count. If the condition can improve as the window grows, this template does not apply.

7. Key takeaways

1. Grow always, shrink while invalid, measure when valid. That order is the template.
2. len(map) is the distinct count only if you delete at zero.
3. Write while, not if — it costs nothing here and saves you on the next problem.
4. O(n) comes from monotonic pointers, not from the technique's name. Be able to say why.
5. This template is a family, not a problem. Recognise k = 1, k = 2 and "exactly k" variants as the same code.
6. Why interviewers like it: it is short enough to write in three minutes, which means the whole conversation is about your invariant, your amortisation argument, and whether you noticed the deletion.

Order: Longest Substring with At Most Two Distinct Characters → Longest Substring with At Most K Distinct Characters.