Grow and Shrink: The Longest Stretch Without Repeats
A music app logs the songs a listener played, in order: A, B, C, B, D, A, E. The app wants the longest stretch of consecutive plays in which no song repeats, to measure how varied a session was. Checking every stretch means about n² stretches, each needing its own check. A window that grows on the right and shrinks on the left does it in one walk.
The rule
Grow the right edge; shrink the left until the window is valid again.
A variable window has no fixed size. Its right edge moves forward one item every step. When the new item breaks the rule ("no repeats"), the left edge moves forward, dropping items, until the rule holds again. After each step the window is the longest valid stretch ending at the right edge, so the best of those is the answer.
def longest_unique_run(plays):
inside = set() # what the window holds right now
left = best = 0
for right, song in enumerate(plays):
while song in inside: # the newcomer would repeat: shrink
inside.remove(plays[left])
left += 1
inside.add(song)
best = max(best, right - left + 1)
return bestThere is a while inside a for, yet it is not n². Each song enters the window once, when right reaches it, and leaves at most once, when left passes it. That is at most 2n moves in total. The set gives an instant answer to "is it already inside?"
The pattern works because of one property: if a window is valid, every smaller window inside it is valid too. A stretch with no repeats stays free of repeats when you drop songs from its left. That is what makes shrinking safe, and it is the first thing to check before using a variable window.
The shortcut
Every variable window is the same loop with three blanks to fill: what the window tracks (here, a set), when it is invalid (the newcomer is already inside), and what to record (the window's length). Fill the blanks and the loop writes itself.
A, B, C
No repeats. The window grows to A B C: length 3.
The trap is shrinking by only one step. When B arrived, dropping A alone was not enough: the old B was still inside. Shrink with while, not if.
Drills
Answer fast — trust the rule.
What does longest_unique_run("AAAA") return?
What does longest_unique_run("ABCDB") return?
In "A, B, C, B, D, A, E", how many songs leave the window when the second B arrives?
The code has a while inside a for. Why is it still about n steps overall?
Remember
- Grow the right edge; shrink the left until the window is valid again.
- Shortcut: fill three blanks: what it tracks, when it is invalid, what to record.
- Trap: shrinking with
ifinstead ofwhile.