Variable-size sliding window

Problem

"Longest substring with no repeated letter", "shortest run of numbers adding to at least a target", "longest stretch that becomes uniform after k edits": every candidate is a contiguous range, and there are about n²/2 of them. Checking each from scratch is cubic or quadratic. The structure that rescues you is monotonicity: if a range is valid, shrinking it keeps it valid (or if it is invalid, growing it keeps it invalid), so you never need to look at a left edge again once it has been passed.

Intuition

Picture an inchworm on a number line. The head (right edge) always steps forward. The tail (left edge) only ever catches up. After every head step you ask whether the worm is still allowed to be this long, and if not, you pull the tail forward until it is. The worm never goes backwards, so head and tail together take at most 2n steps, however the condition behaves in between.

The skill is in two choices: what summary of the window lets you test the condition in O(1) (a set, a count map, a sum, a max count), and which direction of the condition is monotonic, which tells you whether to shrink while invalid (longest) or while valid (shortest).

One row per right-edge step. Amber is the window; green is the longest one found. Watch the left edge jump over the earlier copy of a repeated letter.

Mechanics

The invariant

After each iteration, [left, right] is the longest valid window ending at right (for "longest" problems) or, for "shortest" problems, the longest invalid window ending at right, so that [left - 1, right] is the shortest valid one whenever one exists. The proof has two halves. Safety: the left edge only moves past positions that cannot start a valid window ending at this or any later right edge, because validity is monotonic. Progress: left and right each only increase and are bounded by n, so the loop body runs O(n) times in total even though it contains an inner while. This is amortised analysis: the inner loop's total work is the total distance the left edge travels.

Two templates

Longest: add nums[right]; while the window is invalid, remove nums[left] and advance; then record the length. The record sits after the shrink because only then is the window valid.

Shortest: add nums[right]; while the window is valid, record the length, remove nums[left] and advance. The record sits inside the shrink because each valid state is a candidate and the shrink looks for a smaller one.

A window whose condition is a formula

Replacement problems turn "can I make this window all one letter with at most k edits" into arithmetic. The cheapest plan keeps the most common letter and rewrites the rest, so the cost is length − top count. The window is valid while that cost is at most k. Because the cost can only be computed from counts that update in O(1), no scan of the window is needed.

Bar height is the edit cost after shrinking; the first number under each bar is the window length, the second the letter that just arrived. The cost never crosses the limit.

Worked example

Longest window with no repeated letter in abcbdace. The left edge jumps to one past the previous copy of the arriving letter.

The longest window is bdace, 5 letters, from a single pass of 8 steps.

Shortest run with sum at least 11 in [3, 1, 4, 1, 2, 9, 1, 6]. Every row is a valid window that the shrink loop then tries to make smaller.

The shortest valid run is 2 long, at indices 4 to 5.

Longest stretch fixable with 2 edits in ABAABCBBA:

The best window is 5 letters long.

Implementation

def longest_unique(s):
    last = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1                 # jump past the earlier copy
        last[ch] = right
        best = max(best, right - left + 1)
    return best


def shortest_at_least(target, nums):           # nums must be positive
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best


def longest_after_replacements(s, k):
    counts = {}
    left = best = 0
    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1
        while (right - left + 1) - max(counts.values()) > k:
            counts[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Variations and edge cases

• Covering a multiset. The "smallest window containing every needed letter" problem keeps a need-count map and a single integer, how many letters still lack their quota, like the mismatch counter of the fixed window. Shrink while that integer is zero, recording each state.
• At most k distinct. Keep a count map; the window is invalid when len(counts) > k; delete keys that reach zero, or the length of the map lies.
• Exactly k. Count windows with at most k, subtract those with at most k − 1.
• Max-count shortcut. In the replacement problem the top count can be kept as a value that never decreases and the answer stays right, because only a larger top count can produce a longer window. Calling max over at most 26 counts is simpler and safe.
• Jump versus step. The last-seen map lets the left edge leap; stepping one at a time with a set is also O(n) overall. Check last[ch] >= left, or an old copy outside the window will drag the edge backwards.
• Edge cases: empty input, a target that is never reached (answer 0, not infinity), a single element that already meets the target, all elements equal, and negative numbers, which require prefix sums instead.

Complexity and tradeoffs

• Time: O(n) edge moves in total, with O(1) work per move for sums, sets and count maps. The replacement version costs O(alphabet) per step if you recompute the max.
• Space: O(1) for a sum, O(alphabet) or O(distinct values) for sets and maps.
• Baseline. Trying every pair of edges with an O(n) validity check is O(n³); caching a running summary gets O(n²); the window gets O(n).
• When it fails. Validity must be monotonic in the window's extent. A sum target with negative numbers is not, which is why those questions use prefix sums and a hash map. A condition that depends on the window's median or an arbitrary property needs a different structure, such as a sorted container or two heaps.

Problems

The home problems are the classics of the pattern: a no-repeat window, a smallest covering window, a positive-sum window, a cost-formula window and a restart-on-break scan. The turbulent subarray is the odd one out: its "window" is the current alternating run, which restarts instead of shrinking.

Medium

• 3. Longest Substring Without Repeating Characters Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Keep a window with no repeated characters, jumping its left edge past the previous copy of whatever character just arrived.
• 209. Minimum Size Subarray Sum NeetCode 250
  With positive numbers, grow the window until its sum reaches the target, then shrink it from the left while it still does.
• 424. Longest Repeating Character Replacement Blind 75 Grind 169 NeetCode 150 NeetCode 250
  A window is valid while its length minus its most frequent character's count is at most k, so slide while tracking that count.
• 978. Longest Turbulent Subarray NeetCode 250
  Extend the window while the comparisons keep alternating and restart it at the point where they stop.

Hard

• 76. Minimum Window Substring Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Grow the right edge until the window covers every needed count, then shrink from the left while it still does, recording the smallest.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 1871. Jump Game VII Medium

Connections

This is the fixed window with the width released. The need-count map is the counting page's frequency map; the last-seen jump is the hash map's lookup. When the sum has negative numbers, the prefix sums page takes over. The monotonic deque later handles windows whose summary is a maximum.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms: the aggregate method of amortised analysis (chapter 16 in the fourth edition), which is the proof that the two edges together move O(n) steps.
• Skiena, The Algorithm Design Manual: the discussion of scanning with two moving indices and of loop invariants.
• Sedgewick and Wayne, Algorithms, section 1.4 (analysis of algorithms), including amortized analysis, the argument behind the window's O(n) total.
• Bentley, Programming Pearls, column 8 on the maximum-subarray problem, the best-known linear scan that works on arrays with negative numbers, where windows do not.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.