# Sliding Windows — DSA Interview Patterns

Source: https://www.skillbyai.com/en/dsa-interview-patterns/w-window

> Grow and shrink a range.

## Fixed and variable windows

A **fixed-size window** slides by adding the new element and removing the old one, so each window costs O(1). A **variable window** expands the right edge and shrinks the left edge while a condition is violated (a repeated character, a sum above a limit), tracking the best valid window. Every index enters and leaves once, so the total is O(n).

## Longest substring without repeats and maximum fixed-window sum, run

I ran this with Python 3.12.3 (standard library only). The variable window returns the actual substring for each test, including the empty string; the best sum of three consecutive numbers is 9 (5 + 1 + 3).

```python
# Variable sliding window: longest substring without repeating characters
def longest_unique(s):
    last, start, best = {}, 0, (0, 0)
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start:
            start = last[ch] + 1         # shrink past the previous occurrence
        last[ch] = i
        if i - start + 1 > best[1] - best[0]:
            best = (start, i + 1)
    return s[best[0]:best[1]]

# Fixed window: maximum sum of any k consecutive numbers
def max_window_sum(nums, k):
    cur = best = sum(nums[:k])
    for i in range(k, len(nums)):
        cur += nums[i] - nums[i - k]
        best = max(best, cur)
    return best

for s in ("abcabcbb", "bbbbb", "pwwkew", ""):
    print(repr(s), "->", repr(longest_unique(s)))
print(max_window_sum([2, 1, 5, 1, 3, 2], 3))
```

Output:

```
'abcabcbb' -> 'abc'
'bbbbb' -> 'b'
'pwwkew' -> 'wke'
'' -> ''
9
```

## Write the invariant down

"The window [start, i] has no repeated characters" makes the shrinking rule obvious.

**Quiz:** Why is a variable sliding window O(n) despite having a nested shrink step?

- [ ] Python optimises it
- [ ] The inner loop never runs
- [x] Each index is added and removed at most once
- [ ] Because the input is sorted

*Answer:* Each index is added and removed at most once. Amortised analysis.