The Anatomy of a Sliding Window

The intuition

Think of a window as a conveyor-belt view over the input. The right pointer is the "in-feed"; the left pointer is the "out-feed". An element enters the window when the right pointer moves past it and leaves when the left pointer moves past it. Crucially, each element enters exactly once and leaves at most once. That's where the O(n) time bound comes from: the total work across all iterations is bounded by 2n, because each of n elements contributes at most one "enter" operation and one "leave" operation.

This observation is also what makes the "amortised" complexity argument honest. A single iteration of the outer loop might do many inner-loop iterations, but over the whole run, those inner iterations can't exceed n, because the left pointer never moves backward. The bound is not a promise for each step; it's a promise for the total.

The template, precisely

Almost every sliding-window solution fits this skeleton:

def sliding_window(xs, ...):
    l = 0
    state = fresh()             # hash map, counter, running sum...
    answer = init()
    for r, x in enumerate(xs):
        include(x, state)       # extend window rightward by one

        while not valid(state):
            exclude(xs[l], state)
            l += 1              # contract from the left

        # At this point, [l..r] is the largest valid window ending at r.
        answer = update(answer, l, r, state)
    return answer

Fill in five things per problem: the shape of state, the include update, the exclude update, the valid predicate, and the update of the running answer. Everything else is shared.

Problem 1. Longest substring with at most K distinct characters

Given a string and an integer K, find the length of the longest substring containing at most K distinct characters. Brute force is O(n²). Sliding window is O(n).

def longest_at_most_k_distinct(s, k):
    from collections import defaultdict
    freq = defaultdict(int)
    l = best = 0
    for r, c in enumerate(s):
        freq[c] += 1
        while len(freq) > k:
            freq[s[l]] -= 1
            if freq[s[l]] == 0: del freq[s[l]]
            l += 1
        best = max(best, r - l + 1)
    return best

Correctness: After the while loop, the window contains at most K distinct characters, the invariant holds. The window ending at r is maximal, because extending it leftward would revert the very contractions we just performed. Complexity: each character is included once and excluded at most once, so the total work is O(n). The del when a count reaches zero is not decoration, without it, len(freq) counts stale keys and the invariant check breaks.

Problem 2. Minimum window substring

Given a string s and a pattern t, find the shortest substring of s that contains every character of t (with multiplicity). Brute force is O(n²·m). Sliding window is O(n + m).

def min_window(s, t):
    from collections import Counter
    need = Counter(t)
    missing = len(t)                # total chars still needed
    l = best_l = 0
    best_len = float('inf')
    for r, c in enumerate(s):
        if need[c] > 0: missing -= 1
        need[c] -= 1

        if missing == 0:            # window covers t - try to shrink
            while need[s[l]] < 0:   # slack on left edge
                need[s[l]] += 1
                l += 1
            if r - l + 1 < best_len:
                best_len = r - l + 1
                best_l = l
    return "" if best_len == float('inf') else s[best_l:best_l + best_len]

State: a counter need[c] that tracks, for each character, how many more copies the window still owes. Positive values mean "still need"; zero means "exactly covered"; negative means "have slack". Invariant: when missing == 0, the window covers t. Contraction: the inner while advances the left pointer as long as the character falling off has slack, i.e., its count is negative. The first time a required character hits zero slack, we stop; contracting further would break coverage. Complexity: each index is entered and exited at most once; O(n + m) total.

Problem 3. Longest repeating character replacement

Given a string of uppercase letters and an integer K, you may replace up to K characters with any other character. Find the length of the longest substring consisting of a single repeated character after replacement. Brute force is O(n²·k). Sliding window is O(n).

def character_replacement(s, k):
    counts = [0] * 26
    l = best = 0
    max_count = 0                   # highest count of any single char in the window
    for r, c in enumerate(s):
        counts[ord(c) - 65] += 1
        max_count = max(max_count, counts[ord(c) - 65])

        # window size - max_count = chars that must be replaced
        if (r - l + 1) - max_count > k:
            counts[ord(s[l]) - 65] -= 1
            l += 1                  # only one step - we shrink lazily

        best = max(best, r - l + 1)
    return best

Key insight: the window is valid when window_size − max_count ≤ k, because we'd need exactly that many replacements to make the whole window the majority character. When the window becomes invalid, we shrink by exactly one step, the window size only grows when valid, and the max_count variable is allowed to stay stale (it's an overestimate, but that's harmless; an overestimate only makes the shrink condition easier to satisfy). This is an unusually clever instance of the template: max_count is not recomputed on contraction, and that's deliberate.

The shape, in one sentence

A sliding window solves "longest / shortest / count of contiguous subarrays satisfying property P" in O(n) when P has a monotone invariant, that is, when adding elements can only make the window less valid, and removing them can only make it more valid, or vice versa. That monotonicity is the mechanism that lets the left pointer never move backward. If the problem lacks monotonicity, the pattern does not apply.

Continue

Return to the module page (Module 09 · Two Pointers & Sliding Window) for the broader context, or try the worked problem Two Sum for a converging-pointer exercise.