algo-sliding-window

name	algo-sliding-window
description	Sliding window — fixed and variable size, expand-shrink invariant, hash-state-tracking for substring problems.
when-to-use	Longest/shortest substring with constraint, k-distinct elements, max sum subarray of size k, anagram windows.

Sliding window — expand right, shrink left

Sliding window collapses an O(n^2) "try every subarray" loop into O(n) by reusing partial state across moves. The trick: the window is contiguous and you keep enough state about the window to update it in O(1) (or O(k) for k distinct keys) per step.

Invariants

• The window [l, r] is contiguous — no skipping.
• r advances by 1 each outer iteration.
• l advances only when the window state violates the constraint. Once advanced, it never moves back.
• state(window) is maintained incrementally: add arr[r] on expand, subtract arr[l] on shrink.

Complexity

• Time: O(n) amortised — each element is pushed once and popped at most once across the whole scan.
• Space: O(k) for the state (e.g., a counter dict for distinct characters).

Template — Python (variable-size, longest substring with k distinct chars)

def longest_k_distinct(s: str, k: int) -> int:
    """Length of the longest substring with at most k distinct characters."""
    from collections import Counter
    counts: Counter[str] = Counter()
    best = l = 0
    for r, ch in enumerate(s):
        counts[ch] += 1
        while len(counts) > k:
            counts[s[l]] -= 1
            if counts[s[l]] == 0:
                del counts[s[l]]
            l += 1
        best = max(best, r - l + 1)
    return best

The shrink loop keeps the invariant len(counts) <= k. The del is critical — without it, counts keeps stale zeroes and the len check fails.

Template — Python (fixed-size window, max sum)

def max_sum_subarray(arr: list[int], k: int) -> int:
    """Maximum sum over any contiguous subarray of length k."""
    if len(arr) < k: return 0
    s = sum(arr[:k])
    best = s
    for r in range(k, len(arr)):
        s += arr[r] - arr[r - k]   # roll the window
        best = max(best, s)
    return best

For fixed-size windows, the "subtract the leaver, add the joiner" trick eliminates the inner loop entirely.

Template — JavaScript (anagram-window detection)

function findAnagrams(s, p) {
  if (p.length > s.length) return [];
  const need = new Map();
  for (const c of p) need.set(c, (need.get(c) || 0) + 1);
  const have = new Map();
  const out = [];
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    have.set(c, (have.get(c) || 0) + 1);
    if (r - p.length >= 0) {
      const left = s[r - p.length];
      have.set(left, have.get(left) - 1);
      if (have.get(left) === 0) have.delete(left);
    }
    // Compare maps by size + entries.
    if (have.size === need.size &&
        [...need].every(([k, v]) => have.get(k) === v)) {
      out.push(r - p.length + 1);
    }
  }
  return out;
}

The window slides by exactly one each step; comparison is O(σ) where σ is the alphabet size — for ASCII, effectively constant.

Common pitfalls

• Shrinking too aggressively. Some problems want the shrink to stop the moment the constraint is repaired (while > k), not after one step (if > k). Off by one breaks "longest".
• Forgetting to update the answer at every r. "Longest" problems update inside the outer loop, after the shrink. "Number of substrings" updates differently (count r - l + 1 after shrink — see "subarrays with at most k distinct").
• Stale zero counts. Letting counts[c] == 0 linger inflates len(counts) and breaks the constraint check. Delete on zero.
• Negative numbers + monotonic shrink. Sliding window on arbitrary signs does not always work — adding a negative number can shrink the sum, breaking the monotone-shrink property. Consider prefix-sum + monotonic queue / deque instead.
• Fixed-window length larger than input. Guard with if len(arr) < k.

Test corner cases

• Empty input / k larger than n.
• k == 0 (degenerate — define behaviour explicitly).
• All-same characters.
• Alphabet larger than string length.
• Window straddling the very end of the input.
• "At most k distinct" with k == n (whole string is the window).

If the constraint is "at most k of X", sliding window is usually the right tool. If the constraint involves a non-monotonic function, reach for prefix-sum + monotonic deque instead.