Sliding Window

A window that only ever grows on the right and shrinks on the left — each edge crosses every position at most once, so the whole scan is O(n).