The longest run with only two kinds
A packing line can hold two product types at once before it has to be cleaned down. Given the day’s sequence, find the longest run it could have handled without a change-over.
- A run is a stretch of consecutive items.
- The run may contain at most two distinct characters; one kind, or none, is also fine.
- Return the length of the longest such run.
- An empty sequence has a longest run of zero.
longest_two_flavour_run(sequence: string) → int
Where you start
def longest_two_flavour_run(sequence: str) -> int:
Worked examples
| Call | Result |
|---|---|
longest_two_flavour_run("aabbcc") | 4 |
longest_two_flavour_run("abcbbbbcccbdddadacb") | 10 |
longest_two_flavour_run("aaaa") | 4 |
longest_two_flavour_run("ab") | 2 |
Hint
Grow a window to the right, keeping a count per character inside it. When a third kind appears, pull the left edge in until one kind is gone.
Reference solution in Python
def longest_two_flavour_run(sequence: str) -> int:
counts = {}
left = 0
best = 0
for right, ch in enumerate(sequence):
counts[ch] = counts.get(ch, 0) + 1
while len(counts) > 2:
out = sequence[left]
counts[out] -= 1
if counts[out] == 0:
del counts[out]
left += 1
best = max(best, right - left + 1)
return best