Sliding Window

Back to Index

Use when: finding a subarray/substring that satisfies a condition, often optimal contiguous range problems.

Signal words: subarray, substring, contiguous, maximum/minimum window, at most K distinct.

Core Idea

Maintain a window [left, right] and expand/shrink it instead of recomputing from scratch.

• Fixed window: slide right and left together, window size is constant
• Variable window: expand right freely, shrink left when constraint is violated

Template

left = 0
window = {}  # or a counter, or just a variable
 
for right in range(len(s)):
    # add s[right] to window
    window[s[right]] = window.get(s[right], 0) + 1
 
    while <window violates constraint>:
        # remove s[left] from window
        window[s[left]] -= 1
        if window[s[left]] == 0:
            del window[s[left]]
        left += 1
 
    # update answer with current valid window
    ans = max(ans, right - left + 1)

Key Questions to Ask

• What does the window represent?
• What is the constraint that tells me to shrink?
• Am I looking for max window, min window, or count of valid windows?

---

Problems Using This Pattern

Obsidian will show backlinks here automatically. Any problem note that links to [[Sliding Window]] appears in the graph.