Lessons · Python · the sliding window
A window that grows and shrinks
Keep a start and an end over the same sequence. The end always moves forward; the start moves forward only when the window has broken a rule. The items between them are the window.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
It is the answer to almost every question about the best CONTIGUOUS run: the longest stretch without a repeat, the smallest stretch containing everything, the best sum of any k in a row.
How to think about it
Find the word 'contiguous', or a substring, or 'in a row'. Then name the rule the window must obey, advance the end one item at a time, and while the rule is broken, advance the start.
Worked example
def longest_under(nums, cap):The longest run in a row whose total stays within cap.
start = total = best = 0The window start, what is inside it, and the answer so far.
for end, n in enumerate(nums):The end moves forward once per item and never goes back.
total += nTake the new item in first, even if it breaks the rule.
while total > cap:Broken. Shrink from the left until it holds again.
total -= nums[start]Give back whatever the start was holding…
start += 1…and move it up. Forward only, the same as the end.
best = max(best, end - start + 1)The window is legal again, so now it may count.
return best
print(longest_under([1, 2, 3, 4], 5))2
print(longest_under([], 5))0
Your turn
Shrink the window past the repeated character.
if ch in last_seen and last_seen[ch] >= start:
start = + 1Solve one with the tests running
The trap
It looks like a nested loop and is not. Each end moves forward at most n times across the whole run, so the total is one pass, not n squared.