# Sliding Window — Part 1: The Pattern

A sliding window keeps a **contiguous range `[left, right]`** and updates its state incrementally instead of recomputing it for every subarray. The right edge expands one step at a time; the left edge moves forward only when the window becomes invalid. Since both edges only move forward, the whole scan is **O(n)**, compared with O(n²) or O(n³) for checking every subarray.

![A window over a string expanding on the right and shrinking on the left](diagrams/01-sliding-window.svg)

## 1. Recognition Cues

- "longest / shortest / maximum / minimum **contiguous** subarray or substring such that…"
- "at most k distinct", "without repeating characters", "with sum ≥ target", "containing all characters of t"
- "every window of size k" (fixed window)

The key requirement: **validity must be monotonic**. If a window is invalid, every larger window containing it is also invalid (for "longest" problems), so shrinking is always the right move. With negative numbers and an exact-sum condition this breaks; use **prefix sums + hash map** instead (`04-prefix_sums`).

## 2. Templates

Variable window for "longest valid" problems, and a fixed-size window:

```typescript
function longestAtMostKDistinct(s: string, k: number): number {
  const counts = new Map<string, number>();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    counts.set(s[right], (counts.get(s[right]) ?? 0) + 1);
    while (counts.size > k) {
      const d = s[left++];
      counts.set(d, counts.get(d)! - 1);
      if (counts.get(d) === 0) counts.delete(d);
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

function maxSumFixed(nums: number[], k: number): number {
  let window = nums.slice(0, k).reduce((a, b) => a + b, 0), best = window;
  for (let i = k; i < nums.length; i++) {
    window += nums[i] - nums[i - k];
    best = Math.max(best, window);
  }
  return best;
}
```

```python
def longest_at_most_k_distinct(s, k):
    counts = {}
    left = best = 0
    for right, c in enumerate(s):
        counts[c] = counts.get(c, 0) + 1          # 1. expand: add s[right]
        while len(counts) > k:                    # 2. shrink while invalid
            d = s[left]
            counts[d] -= 1
            if counts[d] == 0:
                del counts[d]
            left += 1
        best = max(best, right - left + 1)        # 3. window [left, right] is valid
    return best

def max_sum_fixed(nums, k):                       # fixed-size window
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]           # add the new, drop the old
        best = max(best, window)
    return best
```

For **"shortest valid"** problems (minimum window, minimum size subarray), the loop flips: expand until the window is valid, then shrink **while it stays valid**, recording the answer inside the shrinking loop.

```text
longest:   for right: add(right); while invalid: remove(left++); best = max(best, len)
shortest:  for right: add(right); while valid:   best = min(best, len); remove(left++)
```

## 3. What Goes in the Window State

| Condition | State to maintain |
|---|---|
| sum of window | a running sum |
| distinct characters | map char → count (its size = distinct count) |
| no repeats | set, or map char → last index (lets you jump `left`) |
| "contains all of t" | need-counts for t + a counter of how many requirements are met |
| most frequent char in window | counts + running `maxFreq` (Longest Repeating Character Replacement) |

## 4. The Last-Index Jump Optimization

For "longest substring without repeating characters", store each character's last index. When `s[right]` was seen inside the window, jump `left = lastIndex[s[right]] + 1` instead of shrinking one by one. The complexity stays O(n), but the code is shorter. Remember to only jump **forward**: `left = max(left, last[c] + 1)`.

## Under the Hood: Why It's O(n)

Each index enters the window once (when `right` reaches it) and leaves at most once (when `left` passes it). The inner `while` loop's iterations, summed across the whole run, are at most n. So the total work is O(n) amortized, plus O(1) per state update if the state is a hash map or counter. This is the argument interviewers expect when they ask "isn't that nested loop O(n²)?"

## Common Pitfalls

1. **Using a window when validity isn't monotonic** (negative numbers with an exact target sum).
2. **Updating the answer at the wrong time:** after shrinking for "longest", inside the shrink loop for "shortest".
3. **Forgetting to delete zero counts** from the map, so `len(counts)` over-reports distinct characters.
4. **Moving `left` backwards** with the last-index jump.
5. **Off-by-one window length:** `right - left + 1`.

## Quick Reference

```text
Longest valid:  expand right; while invalid → shrink left; record after
Shortest valid: expand right; while valid → record, shrink left
Fixed size k:   window += a[i] - a[i-k]
State: sum · counts map · last-index map · "requirements met" counter
O(n) time · O(k) or O(alphabet) space
```