Sliding Window

A window [left, right] covers a contiguous subarray/substring. Instead of rebuilding the answer for every window (O(n^2)/O(n^3)), keep a running summary (sum, set, or counts) and update it in O(1) as the window moves — one pass, O(n).

Fixed-size window

• Width k never changes; neighbouring windows overlap in all but two elements.
• Compute the first window once, then each step: add the entering element, subtract the leaving one (nums[right] - nums[right - k]).
• Time O(n), space O(1).

window += nums[right]
window -= nums[right - k]
best = max(best, window)

Variable-size window (expand / shrink)

• Expand: right++, add the new element to the summary.
• Shrink: while the window breaks the rule, left++ and drop that element, until valid again.
• Keep an invariant (e.g. “no repeated char”) and record the answer only when it holds: after the shrink for longest-valid, inside the shrink for shortest-valid.
• Still O(n): each marker only moves forward, at most n steps each.

seen = set()
left = 0
for right in range(len(s)):
    while s[right] in seen:      # invariant broken
        seen.remove(s[left]); left += 1
    seen.add(s[right])
    best = max(best, right - left + 1)   # width = right - left + 1

• Last-seen dict variant jumps left = last_seen[c] + 1, but only when last_seen[c] >= left (ignore a copy that already left the window).

Counts as window state

• When the rule is about how many of each item, hold a Counter; window is valid when its counts match a target (window == need).
• On each slide: window[incoming] += 1, window[outgoing] -= 1, and del a key when it hits 0 so == stays exact.

Where it breaks

• Needs a monotonic relationship: one element entering must push the constraint only one way (e.g. positive numbers -> sum only grows).
• Negative numbers break the sum-window: min_window_sum([3, -2, 5], 4) returns 3, but the true smallest window is [5], length 1. Use prefix sums + a hash map instead.

Pitfalls

• Shrink with while, not if (may need to drop several elements).
• Width is right - left + 1 (not right - left).
• Never let left move backward; measure only when the invariant holds.

Summary table