Pattern #01

Sliding Window

Essential

Longest, shortest, or valid contiguous ranges over arrays and strings.

When to use

Use when the problem asks for a longest, shortest, or valid contiguous subarray/substring. never when order can be rearranged freely.

Recognition cues

Contiguous subarray or substring
Longest / shortest / at most K / exactly K
Expand right, shrink left while maintaining a window invariant

Common pitfalls

Off-by-one when updating best length (right - left + 1)
Forgetting to update the map/counter when shrinking
Using sliding window when indices need not be contiguous

90-second recognition drill

Which pattern fits best?

Contiguous subarray or substring
Longest / shortest / at most K / exactly K
Expand right, shrink left while maintaining a window invariant

Two PointersMonotonic StackQuick SelectSliding Window

Interactive

Mental model

A full worked walkthrough of the invariant. Pause, scrub the dots, or use ← →. Aim to narrate each step yourself.

Step 1 of 9

best = 0

Start with an empty window. Invariant: all characters unique.

How to think about it

Keep a window [left, right] over the sequence. Expand right one step at a time; shrink left whenever the window breaks its invariant (too many distinct chars, sum too large, missing required chars, …). Track the best valid window as you go. The animation above is the whole idea: grow, fix, record.

Template shapes

Shape	When	Shrink rule
Max window	longest valid	shrink while invalid
Min window	shortest covering constraint	shrink while valid
Fixed size	window of size `k`	advance both ends

Complexity baseline

Typically O(n) time (each index enters/leaves at most once) and O(Σ) space for a frequency map over the alphabet.

From template to problem

Define the invariant (what makes a window valid?).
Choose expand/shrink direction for max vs min.
Decide window state (count map, sum, distinct set, …).
Update the answer only when the invariant holds.

Template

Same skeleton in TypeScript, Python, and C#. Adapt the invariant; keep the structure.

Sliding Window · Template

/**
 * Sliding window (variable length), longest valid window.
 * Expand `right`, shrink `left` while the invariant breaks, then record the answer.
 *
 * Minimum covering window: shrink while still valid, update `best` only when valid
 * (often start with `best = Infinity`).
 */
function slidingWindow(s: string): number {
  const freq = new Map<string, number>();
  let left = 0;
  let best = 0;

  const windowOk = () => {
    // Replace with the problem invariant (e.g. all unique, sum ≤ k).
    return true;
  };

  for (let right = 0; right < s.length; right++) {
    // 1) expand: add s[right] into window state
    const add = s[right]!;
    freq.set(add, (freq.get(add) ?? 0) + 1);

    // 2) shrink while the invariant is broken
    while (left <= right && !windowOk()) {
      const rem = s[left]!;
      const next = (freq.get(rem) ?? 0) - 1;
      if (next <= 0) freq.delete(rem);
      else freq.set(rem, next);
      left++;
    }

    // 3) window [left, right] is valid, update answer
    best = Math.max(best, right - left + 1);
  }

  return best;
}

export { slidingWindow };

/**
 * Sliding window (variable length), longest valid window.
 * Expand `right`, shrink `left` while the invariant breaks, then record the answer.
 *
 * Minimum covering window: shrink while still valid, update `best` only when valid
 * (often start with `best = Infinity`).
 */
function slidingWindow(s: string): number {
  const freq = new Map<string, number>();
  let left = 0;
  let best = 0;

  const windowOk = () => {
    // Replace with the problem invariant (e.g. all unique, sum ≤ k).
    return true;
  };

  for (let right = 0; right < s.length; right++) {
    // 1) expand: add s[right] into window state
    const add = s[right]!;
    freq.set(add, (freq.get(add) ?? 0) + 1);

    // 2) shrink while the invariant is broken
    while (left <= right && !windowOk()) {
      const rem = s[left]!;
      const next = (freq.get(rem) ?? 0) - 1;
      if (next <= 0) freq.delete(rem);
      else freq.set(rem, next);
      left++;
    }

    // 3) window [left, right] is valid, update answer
    best = Math.max(best, right - left + 1);
  }

  return best;
}

export { slidingWindow };

Path

Start path View in problem browser →

#ProblemTypeDifficultyDone

1#3 Longest Substring Without Repeating CharactersGuidemedium
2#76 Minimum Window SubstringGuidehard
3#209 Minimum Size Subarray SumGuidemedium
4#424 Longest Repeating Character ReplacementGuidemedium
5#567 Permutation in StringGuidemedium
6#904 Fruit Into BasketsGuidemedium