pattern heroPT–23LeetCode Extension

Sliding window

Treat a stretch of the data as a window that slides forward: an item comes in at one edge and leaves at the other. The window is never rebuilt from scratch, so the data is walked once instead of trying every stretch.

Variant
P03 Sliding windowVariable size · 1×

Example problem: the longest part of "abacdecf" with no repeated letters.

0a1b2a3c4d5e6c7f
windownext characterbest window

Start with an empty window

window = {}left = –best = –right = –
01/48
restart · back · play · step
Speed
1function longestWithoutRepeats(s):
2 window = empty set
3 left = 0
4 best = 0
5 for right from 0 to len(s) - 1:
6 while s[right] in window:
7 remove s[left] from window
8 left = left + 1
9 add s[right] to window
10 best = max(best, right - left + 1)
11 return best

← → step · space play/pause

How to recognise

a contiguous subarray or substring, the longest or shortest one that meets a condition.

How to solve problems like this

  1. Name the rule a good window follows: no repeats, sum at most k, at most k distinct letters.
  2. Choose what to keep about the window so the rule is quick to check: a set, a map of counts, a running sum.
  3. Grow the window on the right. While it breaks the rule, shrink it from the left.
  4. Update the answer while the window is good: after shrinking for the longest, while shrinking for the shortest.

Variant: Fixed size

The same, but the window keeps its size: each step one item comes in and one leaves. The answer for the window is adjusted from the last one, not counted again.

  1. Check that the window has a fixed length k: k numbers in a row, a substring as long as the pattern.
  2. Choose what to keep about the window so that one item in or out updates it in O(1): a running sum, a map of letter counts.
  3. Build the first window from the first k items and record the answer for it.
  4. Slide: add the item at right, remove the one at right - k, then update the answer. The same works for averages and for anagram windows with letter counts.

Where it's used

  • TCP. A sender may send several packets without waiting for replies, but no more than the window allows. When a confirmation arrives, the window slides forward and the next packets can go.
  • gzip and zip. Their compression, DEFLATE, looks for repeats in the last 32 KB of the text. The window moves along with the text, and a repeat is replaced by a short reference back into it.
  • Rate limits. The rule "no more than 100 requests in the last minute" is a one-minute window that moves with the clock. Cloudflare counts its rate limits this way.