Home / Patterns / Sliding Window

Sliding Window Pattern Hub

5 problems

Best Time to Buy and Sell Stock

easy

TC: O(N) · SC: O(1)

Track `minPrice` seen so far; at each day `p`, candidate profit is `p - minPrice`.

Longest Repeating Character Replacement

medium

TC: O(N) · SC: O(1)

A window `[l..r]` is valid iff `windowLength - maxFreq <= k`. Crucial optimization: never shrink `maxFreq` down when advancing `l`, because a strictly longer window requires a strictly larger `maxFreq`!

Longest Substring Without Repeating Characters

medium

TC: O(N) · SC: O(min(N, Sigma))

Store `{ char: lastIndex }`. When character `c` repeats at `r` and `lastIndex[c] >= l`, jump left pointer directly to `lastIndex[c] + 1` in O(1) instead of creeping `l` step-by-step.

Minimum Window Substring

hard

TC: O(|S| + |T|) · SC: O(|T|)

Maintain `have == need` count of distinct required characters from `t`. Expand `r` until `have == need`, then advance `l` aggressively while maintaining `have == need` and updating the smallest slice.

Permutation in String

medium

TC: O(N) · SC: O(1)

Maintain a fixed window of size `len(s1)` sliding over `s2`, updating character match count `matches` out of 26 in O(1) per slide instead of comparing two 26-arrays every step.