Sliding Windows

Many string and array problems ask you to find some property over every contiguous subrange: the longest substring satisfying a condition, the shortest subarray hitting a target, or every position where a pattern occurs. The brute-force instinct is to check every subrange independently, which usually costs O(n^2) or worse because you recompute the same overlapping work again and again. The sliding window technique fixes this by keeping a single contiguous range, defined by two pointers left and right, and updating it incrementally as it moves across the input instead of restarting from scratch.

The core idea: as right advances one step at a time, you fold the new element into whatever state you are tracking (a running sum, a character frequency map, a count of distinct values). When the window becomes invalid, or when you want to consider a smaller window, you advance left and remove its element from the same state. Because each element is added once and removed at most once, the whole scan runs in O(n) time no matter how many windows you "visit" along the way.

There are two shapes this pattern takes. A fixed-size window has a length decided up front by the problem — for example, "does any substring of length equal to the pattern have the same character counts as the pattern?" Here right and left move in lockstep once the window reaches its target size: for every step forward you take with right, you take exactly one step forward with left afterward, keeping the width constant. A variable-size window instead grows and shrinks based on a condition — for example, "keep expanding right while the window stays valid; when it becomes invalid, shrink from the left until it is valid again." You use a fixed window when the target width is known in advance, and a variable window when you are optimizing for the longest or shortest range satisfying some rule.

The general template for variable-size windows looks like this:

left = 0
state = {}  # e.g. frequency map, running sum, distinct count
for right in range(n):
    add(arr[right], state)          # expand: fold new element in
    while window_is_invalid(state): # shrink while broken
        remove(arr[left], state)
        left += 1
    update_answer(left, right, state)  # window [left, right] is now valid

The key insight that makes this O(n) rather than O(n^2) is that left only ever moves forward — it never resets back to an earlier position — so across the entire run it advances at most n times in total, matched by at most n advances of right.

Complexity. Both window shapes run in O(n) time since each index is touched a constant number of times by each pointer. Space is usually O(k) or O(26) for a frequency map — constant if the alphabet is fixed (e.g., lowercase English letters), or O(min(n, alphabet size)) in general.

Common pitfalls. A frequent bug is shrinking with the wrong condition — for example checking while when the fix only needs an if, or vice versa, which silently turns an O(n) solution into O(n^2) or produces wrong answers. Off-by-one errors on window length (right - left + 1 vs right - left) are another classic source of bugs — always double check whether your indices are inclusive. Finally, remember to update all relevant state when an element leaves the window on the left, not just when it enters on the right; forgetting to decrement a count or remove a now-empty key from a map leads to stale state that corrupts later comparisons.

This subject walks through three increasingly involved applications: finding every anagram of a pattern inside a string using a fixed-size window, finding the longest substring with no repeated characters using a variable-size window, and finding the longest substring that can be made uniform with at most k character replacements using a variable-size window that tracks the most frequent character seen so far.