What you will learn
- Fixed-size versus variable-size windows.
- The grow-right, shrink-left template.
- Minimum window substring, a classic hard problem, step by step.
Signals
- “Contiguous subarray or substring” plus “longest”, “shortest”, “maximum sum”, “at most K distinct”.
- A brute force that recomputes something for every (start, end) pair.
Two kinds of window
- Fixed size k: slide one step at a time, add the entering element and remove the leaving one. O(n).
- Variable size: expand
rightevery step; while the window breaks (or satisfies) a condition, moveleft. Each index enters and leaves once, so O(n) despite the nested loop.
left = 0
for right, x in enumerate(items):
add(x)
while window_invalid():
remove(items[left])
left += 1
update_answer(left, right)
Code
"""Sliding window: fixed-size and variable-size windows over arrays and strings."""
from collections import Counter
def max_sum_k(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k] # slide: add the new element, drop the old one
best = max(best, window)
return best
def longest_unique_substring(s):
last = {}
left = best = 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1 # jump past the previous copy
last[ch] = right
best = max(best, right - left + 1)
return best
def min_window(s, t):
need, missing = Counter(t), len(t)
left, best = 0, (0, float("inf"))
for right, ch in enumerate(s):
if need[ch] > 0:
missing -= 1
need[ch] -= 1
while missing == 0: # valid window: try to shrink it
if right - left < best[1] - best[0]:
best = (left, right)
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return "" if best[1] == float("inf") else s[best[0]: best[1] + 1]
if __name__ == "__main__":
print(max_sum_k([2, 1, 5, 1, 3, 2], 3))
print(longest_unique_substring("abcabcbb"), longest_unique_substring("pwwkew"))
print(repr(min_window("ADOBECODEBANC", "ABC")))
Output:
9
3 3
'BANC'
- Max sum of k: one running sum, updated in O(1) per step.
- Longest substring without repeats: remember each character’s last index; when it repeats inside the window, jump
leftpast the old copy instead of shrinking one step at a time. - Minimum window substring:
needcounts what’s still required;missingcounts how many characters are outstanding. Whenmissinghits 0 the window is valid, so shrink from the left while it stays valid, recording the smallest.
When sliding window doesn’t apply
The shrink step needs monotonicity: making the window bigger must never make an invalid window valid again (or vice versa). With negative numbers, “subarray sum equals k” breaks that rule, and you need prefix sums instead.
When you need the maximum inside each window, a running variable isn’t enough; that’s the next lesson, sliding window maximum.
Practise: sliding window problems.
Key takeaways
- Fixed windows: add one, remove one. Variable windows: grow right, shrink left while invalid.
- Each index enters and leaves once, so the nested while loop is still O(n).
- Track window state with counts or last-seen indices.
- Sliding window needs monotonic validity; with negative numbers use prefix sums.
Exercises
- Longest substring with at most K distinct characters.
- Longest repeating character replacement (LeetCode 424).
- Find all anagrams of
pinsusing a fixed window of counts.
Quiz
- Why is the variable window O(n) despite a while loop inside a for loop?
- Why can’t sliding window solve “subarray sum equals k” with negative numbers?
- In minimum window substring, what does
missing == 0mean?
Show answers
leftonly moves forward and never pastright, so across the whole run it moves at most n times.- Adding a negative number can make a too-large sum valid again, so shrinking isn’t safely monotonic.
- The current window contains every required character with enough multiplicity, so it’s a valid candidate.