Sliding Window

Fixed and variable windows for subarray and substring problems.

The sliding window pattern handles questions about contiguous subarrays or substrings. Instead of recomputing every window from scratch (O(n²) or worse), you maintain the window's state as it slides: add the element entering on the right, remove the one leaving on the left.

When to use it

"Longest / shortest / count of subarrays or substrings such that…"
The condition can be updated incrementally as elements enter and leave
For variable windows, the condition is monotonic: if a window is valid, shrinking it keeps it valid (or expanding keeps it invalid)

[!WARNING] Negative numbers break it "Subarray with sum k" with negative numbers isn't monotonic — growing the window can decrease the sum. Use prefix sums + a hash map instead (see Hash Maps & Sets).

Fixed-size window

def max_window_sum(nums, k):
    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

Variable-size window: the template

def variable_window(s):
    left = 0
    state = {}           # whatever describes the current window
    best = 0
    for right, ch in enumerate(s):
        # 1. add s[right] to the state
        # 2. while the window is invalid, remove s[left] and advance left
        # 3. the window [left, right] is valid: update the answer
        ...
    return best

Longest substring without repeating characters

def length_of_longest_substring(s):
    last_seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if last_seen.get(ch, -1) >= left:
            left = last_seen[ch] + 1   # jump past the previous occurrence
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

Minimum window containing all target characters

For "shortest" problems, flip the loop: expand until valid, then shrink while still valid, recording the answer during the shrink.

from collections import Counter

def min_window(s, t):
    need = Counter(t)
    missing = len(t)
    left = 0
    best = (float("inf"), 0, 0)
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        while missing == 0:
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right + 1)
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    return s[best[1]:best[2]] if best[0] != float("inf") else ""

Complexity

Each element enters and leaves the window at most once: O(n) time, with O(k) or O(alphabet) space for the window state.

[!TIP] Practice Longest Substring Without Repeating Characters · Minimum Window Substring