Sliding Window

Reuse the work from the last position instead of starting over.

The idea

Picture looking through a frame that shows 3 houses at a time while you walk down a street. To know the total value of the houses in view after one step, you do not re-add all 3: you add the new house that appeared and subtract the one that left.

A window can also grow and shrink: for “longest stretch with no repeated letter”, the right edge grows one letter at a time, and when a repeat appears the left edge jumps forward just far enough to remove it.

Watch it work

Try it

Common mistakes

How fast is it?

Time: O(n) – every item enters the window once and leaves at most once. Space: O(1) for the fixed window; O(alphabet) for the substring version (the map of last-seen positions).