Sliding Window

Updated Nov 19, 2026 · 4 min read
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.

    The string "eceba" with at most 2 distinct letters. Six rows show the window growing to "ece" (length 3), turning red when b makes three letters, then shrinking to "eb" and later "ba". Best is 3.
    The string "eceba" with at most 2 distinct letters. Six rows show the window growing to "ece" (length 3), turning red when b makes three letters, then shrinking to "eb" and later "ba". Best is 3.

    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
    Two code boxes. Longest valid: shrink while invalid, then record. Shortest valid: while valid, record, then shrink. Note: shrinking only works if adding an element can never fix a broken window.
    Two code boxes. Longest valid: shrink while invalid, then record. Shortest valid: while valid, record, then shrink. Note: shrinking only works if adding an element can never fix a broken window.

    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 missing number 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 if instead of while to 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

    1. Best Time to Buy and Sell Stock: the simplest window, where only the lowest price so far matters.
    2. Longest Substring Without Repeating Characters: the longest-valid template.
    3. Longest Repeating Character Replacement: size − max_count ≤ k.
    4. Permutation in String: a fixed window with letter counts.
    5. Max Consecutive Ones III: longest window with at most k zeros.
    6. Minimum Window Substring: the shortest-valid template with a missing counter.
    7. Sliding Window Maximum: a fixed window with a monotonic deque.
    8. 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