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.

See also: Meta Interview Prep

See also: Atlassian Interview Prep

See also: Snap Interview Prep