At most k kinds
The longest stretch of text using at most k different characters. About 10 minutes.
How many kinds are in the window?
A fruit seller can carry at most two kinds of fruit in their basket, and walks past a row of trees. What's the longest stretch of trees they can pick from? That's this problem: the longest window with at most k different characters.
Keep a count for each character in the window. When a count goes from 0 to 1, a new kind has entered. When it drops back to 0, a kind has left.
- best
- 2
- kinds
- 2
- counts
- e1 c1
Grow: e, then c. Two kinds, allowed.
Shrink until it's allowed again
Grow on the right. If that brings in one kind too many, move the left end forward, lowering counts, until one kind has completely disappeared. Then measure the window.
Measuring only after the shrinking means you only ever measure windows that follow the rule. For "eceba" with k = 2, the best is "ece": length 3.
counts = {}
left = best = 0
for right, ch in enumerate(s):
counts[ch] = counts.get(ch, 0) + 1
while len(counts) > k:
counts[s[left]] -= 1
if counts[s[left]] == 0:
del counts[s[left]]
left += 1
best = max(best, right - left + 1)
return bestk is 2. The window holds "aab", and a c arrives. What must happen?
- AMove the left end until a or b is gone
- BDrop just one character
- CStart over at the c
Show the answer
Move the left end until a or b is gone. "aabc" has 3 kinds. Dropping both a's leaves "bc", back to 2.
Longest with at most k kinds
You get a string and k. Return the length of the longest run of consecutive characters that contains at most k different characters.
s = "eceba", k = 2 → 3
0 ≤ length ≤ 100,000 · 0 ≤ k ≤ 100 · printable ASCII characters