Longest stretch with at most two kinds

Sliding window Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
from collections import Counter
belt = [1, 2, 1, 2, 3, 3, 3]
counts: Counter[int] = Counter()
left = best = 0
for right, kind in enumerate(belt):
    counts[kind] += 1
    while len(counts) > 2:
        counts[belt[left]] -= 1
        if counts[belt[left]] == 0:
            del counts[belt[left]]
        left += 1
    best = max(best, right - left + 1)
print(best)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 4

Right: [1, 2, 1, 2] and [2, 3, 3, 3] both have length 4.

Removing kinds until two remain keeps every window valid, and two different stretches tie for the best length.

Why not the others?
  • B 5. Any stretch of 5 here contains all three kinds.
  • C 3. The first four items use only two kinds.

30-second answer

Keep counts of the kinds inside the window. Add each new item; while more than two kinds are present, remove from the left and delete kinds whose count hits zero. The window is always valid after the loop, so track its best length. O(n) time, O(1) extra space for at most three kinds in the map.

Practise saying it · 45 s. No recording, just a timer

Explain the at-most-k-kinds window.

Say your answer out loud, then check which of these points you covered:

  • Counts of kinds in the window
  • Shrink while more than k
  • Delete zero counts

Deep dive

Generalises directly to 'at most k kinds' with the same code.

Deleting zero-count keys keeps len(counts) equal to the number of kinds present.

Each item enters and leaves once: linear time.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def longest_two_kinds(belt: list[int]) -> int:
    counts: dict[int, int] = {}
    left = best = 0
    for right, kind in enumerate(belt):
        counts[kind] = counts.get(kind, 0) + 1
        while len(counts) > 2:
            old = belt[left]
            counts[old] -= 1
            if counts[old] == 0:
                del counts[old]
            left += 1
        best = max(best, right - left + 1)
    return best

Common mistakes

  • Forgetting to delete a kind when its count drops to zero, so the window looks like it still has three kinds.
  • Shrinking only once instead of until two kinds remain.

Senior take & follow-ups

Write it for general k; it shows the pattern, not a one-off trick.

Follow-up questions

Think of your answer first, then open the hint.

  1. What about exactly k kinds?

    Show hint

    Count windows with at most k minus windows with at most k - 1.

  2. Can you store last positions instead of counts?

    Show hint

    Yes: when a third kind arrives, jump left past the earliest last position.

What each operation costs: Arrays · Deque

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.