</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

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.

At most K distinct sliding-window loop flowchart

Worth knowing: this template answers many differently worded problems. Fruit Into Baskets is k = 2 with a story on top, and Subarrays With K Different Integers is this counting function called twice and subtracted. When you meet a new window problem, a useful first question is whether it is at-most-k in disguise.

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


The idea in one line: 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

Two details carry 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 answers come 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.

Worked example trace: longest substring with at most two distinct characters

Two things to notice. The shrink at right = 3 ran twice, because dropping 'e' left three kinds still present. That is the clearest 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.
  • Working-set sizing. The longest stretch of an access trace that touches at most k distinct pages tells you how large a cache of k pages can usefully be.
  • Connection patterns. The longest period during which a client contacted no more than k distinct endpoints.
  • Text and DNA analysis. Longest substring over a restricted alphabet.
  • Inventory constraints. The literal fruit-baskets framing: how much you can collect from consecutive stalls with a limited number of container types.

5. Problems in this chapter

Longest Substring with At Most Two Distinct Characters

The template with k hard-coded to 2. Solve it first: 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. 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.

Max Consecutive Ones II

Longest run of 1s if you may flip a single 0. The same grow-and-shrink loop, with the bound counting zeros instead of distinct values, which is what makes this template a family rather than one problem.
Pattern: grow-and-shrink with a counter. Target: O(n) time, O(1) 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 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.
  • Forgetting k = 0. The answer is 0. The template above gets this right (every arrival is shrunk away at once), but check your own variant; an early return 0 makes the intent obvious.
  • Using it 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 → Max Consecutive Ones II.

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.