Sliding Window — The Complete Guide

function fixedWindow(arr: number[], k: number): Result {
  // 1. Build the first window
  let windowState = initializeWith(arr[0..k-1]);

  // 2. Record answer for first window
  let answer = evaluate(windowState);

  // 3. Slide: add right, remove left
  for (let right = k; right < arr.length; right++) {
    const left = right - k;
    windowState.add(arr[right]);      // element entering
    windowState.remove(arr[left]);    // element leaving
    answer = best(answer, evaluate(windowState));
  }

  return answer;
}
// When to use: "k consecutive elements", "window of size k"
// Key: window size never changes — always exactly k elements

function variableWindow(arr: number[]): Result {
  let left = 0;
  let windowState = {};  // frequency map, sum, count, etc.
  let answer = initialValue;

  for (let right = 0; right < arr.length; right++) {
    // 1. Expand: add arr[right] to window state
    windowState.add(arr[right]);

    // 2. Shrink: while window is INVALID, remove from left
    while (!isValid(windowState)) {
      windowState.remove(arr[left]);
      left++;
    }

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

  return answer;
}
// When to use: "longest/shortest subarray/substring with condition"
// Key: right always moves forward; left only moves forward (never back)
// This guarantees O(n) — each element enters and leaves at most once

function minWindow(arr: number[]): Result {
  let left = 0;
  let windowState = {};
  let answer = Infinity;

  for (let right = 0; right < arr.length; right++) {
    windowState.add(arr[right]);

    // Shrink while window is VALID (to find minimum)
    while (isValid(windowState)) {
      answer = Math.min(answer, right - left + 1);
      windowState.remove(arr[left]);
      left++;
    }
  }

  return answer;
}
// When to use: "minimum window substring", "shortest subarray with sum ≥ target"
// Key difference: shrink while VALID (not while invalid)

function lengthOfLongestSubstring(s: string): number {
  const freq = new Map<string, number>();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    // Expand: add s[right]
    freq.set(s[right], (freq.get(s[right]) ?? 0) + 1);

    // Shrink: while we have a duplicate
    while (freq.get(s[right])! > 1) {
      freq.set(s[left], freq.get(s[left])! - 1);
      if (freq.get(s[left]) === 0) freq.delete(s[left]);
      left++;
    }

    // Update answer
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}
// Time: O(n) — each char enters and leaves the map at most once
// Space: O(min(n, alphabet)) — map holds at most the alphabet size

function characterReplacement(s: string, k: number): number {
  const freq = new Map<string, number>();
  let left = 0;
  let maxFreq = 0; // max frequency of any single char in current window
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    freq.set(s[right], (freq.get(s[right]) ?? 0) + 1);
    maxFreq = Math.max(maxFreq, freq.get(s[right])!);

    // Window is invalid if we need more than k replacements
    // replacements = windowSize - maxFreq
    while ((right - left + 1) - maxFreq > k) {
      freq.set(s[left], freq.get(s[left])! - 1);
      left++;
    }

    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}
// Key insight: we don't need to update maxFreq when shrinking.
// A smaller maxFreq can only shrink the window, never grow it.
// So the answer is still correct — we just skip suboptimal windows.

String: a  b  c  a  b  c  b  b
Index:  0  1  2  3  4  5  6  7

Window state: Set of characters in current window
Goal: longest window with all unique characters

Step 1: right=0, char='a' → Set={a}         window="a"       len=1  max=1
Step 2: right=1, char='b' → Set={a,b}       window="ab"      len=2  max=2
Step 3: right=2, char='c' → Set={a,b,c}     window="abc"     len=3  max=3 ★
Step 4: right=3, char='a' → 'a' in Set!
        Shrink: remove 'a', left=1          Set={b,c}
        Add 'a'                             Set={b,c,a}      window="bca"     len=3  max=3
Step 5: right=4, char='b' → 'b' in Set!
        Shrink: remove 'b', left=2          Set={c,a}
        Add 'b'                             Set={c,a,b}      window="cab"     len=3  max=3
Step 6: right=5, char='c' → 'c' in Set!
        Shrink: remove 'c', left=3          Set={a,b}
        Add 'c'                             Set={a,b,c}      window="abc"     len=3  max=3
Step 7: right=6, char='b' → 'b' in Set!
        Shrink: remove 'a', left=4          Set={b,c}  — still has 'b'!
        Shrink: remove 'b', left=5          Set={c}
        Add 'b'                             Set={c,b}        window="cb"      len=2  max=3
Step 8: right=7, char='b' → 'b' in Set!
        Shrink: remove 'c', left=6          Set={b}  — still has 'b'!
        Shrink: remove 'b', left=7          Set={}
        Add 'b'                             Set={b}          window="b"       len=1  max=3

Answer: 3 ("abc")

Key observations:
- right always moves forward (one step per iteration)
- left only moves forward (never backwards)
- Each character enters the set once and leaves once → O(n) total
- The shrink loop may run multiple times in one step, but total shrinks across ALL steps ≤ n

s: A  D  O  B  E  C  O  D  E  B  A  N  C
   0  1  2  3  4  5  6  7  8  9  10 11 12

Need: {A:1, B:1, C:1}  (3 unique chars to satisfy)
formed = 0 (how many chars are fully satisfied)

Expand right until formed === 3:
  right=0 'A' → have={A:1} → formed=1
  right=1 'D' → have={A:1,D:1}
  right=2 'O' → have={A:1,D:1,O:1}
  right=3 'B' → have={A:1,D:1,O:1,B:1} → formed=2
  right=4 'E' → have={...,E:1}
  right=5 'C' → have={...,C:1} → formed=3 ★ window="ADOBEC" len=6

Shrink left while formed === 3:
  left=0 remove 'A' → have={A:0} → formed=2 → STOP
  Best so far: "ADOBEC" (len=6, start=0)

Continue expanding...
  right=9  'B' → formed=2 still
  right=10 'A' → formed=3 ★ window="CODEBA" → wait, let me shrink...
  
  Shrink: left=1 'D', left=2 'O', left=3 'B' → formed=2 → STOP
  Best: "BANC" is found later at right=12

Final answer: "BANC" (length 4, starting at index 9)

The pattern: expand until valid → shrink while valid → record minimum → repeat

Is the problem about a CONTIGUOUS subarray or substring?
├── NO  → Not Sliding Window. Consider DP, Backtracking, or Hashing.
└── YES → Is the window size fixed (given k)?
          ├── YES → Fixed-Size Window (Template 1)
          │         Add right, remove left, update answer each step.
          └── NO  → Do you need the LONGEST or SHORTEST valid window?
                    ├── LONGEST → Variable Window: shrink while INVALID
                    │             Track max(right - left + 1)
                    └── SHORTEST → Variable Window: shrink while VALID
                                  Track min(right - left + 1)

What's the window state?
├── Sum/count → single variable, O(1) update
├── Character frequencies → hash map, O(1) update per char
├── Distinct count → hash map + map.size
└── Max/min in window → monotonic deque (advanced)