Sliding Window
On this page
A sliding window looks at a contiguous range [left, right] and updates its state as the range moves, instead of recomputing every subarray from scratch. The right edge moves forward every step. The left edge moves forward only when the window breaks a rule. Because neither edge ever goes back, each element enters once and leaves once: O(n) instead of O(n²).
When to recognise it
- The question says substring or subarray (contiguous), and asks for the longest / shortest / maximum / count of ranges with some property.
- "At most k distinct", "no repeating characters", "at most k replacements", "contains all characters of t".
- "Every window of size k": averages, maximums, anagram positions. That is a fixed-size window.
- The validity rule is monotonic: if a window is valid, every smaller window inside it is valid too (or the reverse). If adding an element can fix a broken window, for example with negative numbers in a sum, a window will not work; use Hash Maps and Prefix Sums.
How it works
Keep counts for the current window in a hash map or a fixed array. Each step, add s[right]. While the window is invalid, remove s[left] and move left. Now the window is the longest valid one ending at right, so update the answer.

Template
The "longest valid window" shape:
from collections import defaultdict
def longest_with_at_most_k_distinct(s, k):
"""Variable window, 'longest valid': grow right every step, shrink left while invalid."""
count = defaultdict(int)
left = best = 0
for right, ch in enumerate(s):
count[ch] += 1
while len(count) > k: # window broke the rule: shrink
count[s[left]] -= 1
if count[s[left]] == 0:
del count[s[left]]
left += 1
best = max(best, right - left + 1) # window is valid here
return best
Time O(n), space O(k) for the counts.
The "shortest valid window" shape flips where you record the answer: you shrink while the window is still valid and record each time. This version needs non-negative numbers, so that shrinking can only make the sum smaller:
def shortest_with_sum_at_least(nums, target):
"""Variable window, 'shortest valid' (non-negative numbers): shrink while still valid."""
left = total = 0
best = float('inf')
for right, x in enumerate(nums):
total += x
while total >= target:
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return 0 if best == float('inf') else best

Fixed size. When the size is given, there is nothing to decide: add the new element, drop the one that falls out.
def max_sum_fixed(nums, k):
"""Fixed-size window: add the new element, drop the one that falls out."""
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
best = max(best, window)
return best
How to choose the window state
Ask what you must know to decide whether the window is valid, and make it O(1) to update:
- distinct count → a map of counts, and delete keys that drop to 0 (or track a counter);
- "contains all of t" → counts needed plus a
missingnumber that hits 0 when the window covers t; - "at most k replacements" → counts plus the highest single count; the window is valid while
size − max_count ≤ k; - window maximum → a deque of indices with decreasing values (a monotonic queue, see Stacks and Monotonic Stacks).
Common bugs
- Using
ifinstead ofwhileto shrink. One step may not be enough to make the window valid again. - Recording the answer in the wrong place: for "longest", after shrinking; for "shortest", inside the shrink loop.
- Forgetting to delete zero counts, so
len(count)overcounts distinct letters. - Off-by-one on the size: it is
right − left + 1. - Negative numbers. A sum window breaks: shrinking might raise the sum. Switch to prefix sums.
Say this in the interview
- "Both pointers only move forward, so each character is added and removed at most once. That's O(n) total even though there's a nested while loop."
- "The window stays valid after every step, so at each right edge I have the longest valid window ending there."
Problems for this pattern
- Best Time to Buy and Sell Stock: the simplest window, where only the lowest price so far matters.
- Longest Substring Without Repeating Characters: the longest-valid template.
- Longest Repeating Character Replacement:
size − max_count ≤ k. - Permutation in String: a fixed window with letter counts.
- Max Consecutive Ones III: longest window with at most k zeros.
- Minimum Window Substring: the shortest-valid template with a
missingcounter. - Sliding Window Maximum: a fixed window with a monotonic deque.
- Design Hit Counter: a time window over a queue of hits.
Related
Two Pointers · Hash Maps and Prefix Sums · Stacks and Monotonic Stacks · Arrays and Strings