Sliding Window Interview Patterns: Fixed Window, Variable Window, and String Problems (2025)

The Sliding Window Pattern

Sliding window optimizes O(n^2) brute-force approaches on contiguous subarrays/substrings to O(n). The key insight: instead of recomputing the result for each window from scratch, maintain a running state (sum, character count, etc.) and update it incrementally as the window expands or contracts. Two variants: Fixed-size window: window size k is given. Slide by adding the new element and removing the leftmost. Variable-size window: find the smallest/largest window satisfying a condition. Expand the right pointer; when the condition is violated, shrink from the left. Template: right pointer iterates; left pointer advances only when the window violates the constraint.

Fixed Window: Maximum Sum Subarray of Size K

def max_sum_subarray(nums: list[int], k: int) -> int:
    window_sum = sum(nums[:k])
    max_sum = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]  # add new, remove old
        max_sum = max(max_sum, window_sum)
    return max_sum

Variable Window: Longest Substring Without Repeating Characters (LC 3)

def length_of_longest_substring(s: str) -> int:
    char_index = {}  # last seen index of each char
    left = 0
    max_len = 0
    for right, c in enumerate(s):
        if c in char_index and char_index[c] >= left:
            left = char_index[c] + 1  # shrink: skip past last occurrence
        char_index[c] = right
        max_len = max(max_len, right - left + 1)
    return max_len

Variable Window: Minimum Window Substring (LC 76)

Find the smallest window in s that contains all characters of t. Use a frequency map for t. Expand right pointer, decrement frequency on each match. When all characters of t are satisfied (have count): record window length and advance left pointer to minimize.

from collections import Counter

def min_window(s: str, t: str) -> str:
    need = Counter(t)
    have, total = 0, len(need)
    window = {}
    left = 0
    result = ""
    min_len = float('inf')

    for right, c in enumerate(s):
        window[c] = window.get(c, 0) + 1
        if c in need and window[c] == need[c]:
            have += 1
        while have == total:  # valid window — try to shrink
            if right - left + 1 < min_len:
                min_len = right - left + 1
                result = s[left:right+1]
            lc = s[left]
            window[lc] -= 1
            if lc in need and window[lc] < need[lc]:
                have -= 1
            left += 1
    return result

Longest Subarray with Sum <= K (Variable Window)

def longest_subarray_sum_at_most_k(nums: list[int], k: int) -> int:
    # Works when all nums >= 0
    left = 0
    window_sum = 0
    max_len = 0
    for right in range(len(nums)):
        window_sum += nums[right]
        while window_sum > k:
            window_sum -= nums[left]
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len

Sliding Window Maximum (LC 239) — Monotonic Deque

Find the maximum in each window of size k. Naive: O(nk). Optimal: O(n) using a deque that maintains indices of potentially useful elements in decreasing order of value.

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    dq = deque()  # indices, values are decreasing
    result = []
    for i, n in enumerate(nums):
        # Remove elements outside the window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # Remove elements smaller than n (they can never be max)
        while dq and nums[dq[-1]] = k - 1:
            result.append(nums[dq[0]])  # front is the max
    return result

Key patterns: Longest Subarray with at most K distinct characters (LC 340): expand right; when distinct count > K, shrink left. Count subarrays with exactly K distinct: count(at most K) – count(at most K-1). Permutation in String (LC 567): fixed window of size len(p); check if frequency maps match. Fruit Into Baskets (LC 904): longest subarray with at most 2 distinct values — classic variable window.

{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the sliding window pattern and when does it apply?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The sliding window pattern applies when you need to find or optimize over a contiguous subarray or substring of an array/string. Instead of re-examining every element of each window from scratch (O(nk) brute force), maintain a running state (sum, character frequency map, distinct count) that is updated incrementally as the window moves — adding the new right element and removing the old left element in O(1) per step, giving O(n) total. It applies when: the problem involves subarrays/substrings, the answer can be maintained incrementally, and the constraint is monotonic (making the window larger can only make the constraint harder to satisfy, enabling the shrink step to be safe).”}},{“@type”:”Question”,”name”:”What is the key decision in variable-size sliding window: when to shrink?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The shrink condition is the constraint that the window must satisfy. Expand the right pointer freely; when the constraint is violated, advance the left pointer until the constraint is restored. The critical property: the constraint must be monotonic — if a window of size k violates the constraint, adding more elements (growing) can only make it worse, never better. This guarantees the left pointer never needs to move backward. Examples: "at most K distinct characters" — if distinct > K, shrink. "sum <= K" (with non-negative numbers) — if sum > K, shrink. "no duplicate characters" — if the current char is already in the window, shrink past its previous occurrence. If the constraint is not monotonic (e.g., with negative numbers), sliding window may not apply and a different approach is needed.”}},{“@type”:”Question”,”name”:”How does the monotonic deque solve sliding window maximum in O(n)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A naive sliding window maximum requires O(k) per window to find the max, giving O(nk) total. The monotonic deque maintains the indices of "candidate maximum" elements in decreasing order of value. Invariant: the deque front is always the index of the current window's maximum. On each step: (1) Remove elements outside the window (front of deque < i – k + 1). (2) Remove elements from the back that are <= the new element (they can never be the maximum since the new element is larger and will remain in the window longer). (3) Append the new index. The deque front is the maximum of the current window. Each element is added and removed at most once, giving O(n) total. The deque stores indices (not values) so we can check if an element has left the window.”}},{“@type”:”Question”,”name”:”How do you count subarrays with exactly K distinct integers using sliding window?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Sliding window directly finds longest or shortest subarrays but not "exactly K" counts — because adding elements can both satisfy and violate the constraint non-monotonically. Solution: exactly(K) = atMost(K) – atMost(K-1). atMost(K) counts subarrays with at most K distinct integers. Use sliding window: expand right, track distinct count in a frequency map. When distinct > K: shrink left until distinct <= K. For each right position, the number of valid subarrays ending at right is (right – left + 1). Sum these to get atMost(K). The subtraction converts the at-most count to an exactly count. This pattern generalizes: any "exactly K" constraint on subarrays can be solved as atMost(K) – atMost(K-1) when the at-most version is solvable with sliding window.”}},{“@type”:”Question”,”name”:”What is the difference between the sliding window approach for Minimum Window Substring vs. Permutation in String?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Both use a character frequency map and two pointers, but differ in the validity condition and window structure. Permutation in String (LC 567): fixed window size (len(p)). Slide by adding one character and removing one. Check after each slide if frequency maps match. O(26n) or O(n) depending on comparison method. Minimum Window Substring (LC 76): variable window. Expand right, tracking how many characters from t are satisfied (have count). When all characters are satisfied: record the window and shrink from left to minimize. Continue. The "have == total" condition uses a count of fully-satisfied distinct characters rather than comparing full maps — this reduces the inner condition from O(26) to O(1) per step.”}}]}