backend / dsa / arrays strings / 02_sliding_window.md

Sliding window

4 interview angles 3 min read source

Sliding window

Maintain a window [left, right] over an array/string; grow it by moving right, shrink by moving left. Computes per-window aggregates (sum, count, max) in O(n) by adjusting incrementally instead of recomputing.

When to apply

  • “Find the longest/shortest subarray such that …”
  • “Find the maximum sum of K consecutive elements”
  • “Find substring with property X”
  • Any “contiguous subarray” problem with a monotonic invariant

Pattern: fixed-size window

def max_sum_subarray_k(arr: list[int], k: int) -> int:
    """Max sum of any k consecutive elements."""
    window_sum = sum(arr[:k])
    best = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]   # slide: add new, drop old
        best = max(best, window_sum)
    return best

O(n), O(1) space.

Pattern: variable-size window

def longest_substring_no_repeat(s: str) -> int:
    """Longest substring with all unique characters."""
    seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1     # shrink past the previous occurrence
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

The window expands always (right always advances). It contracts conditionally when the invariant breaks. Each character is visited O(1) times — O(n).

Pattern: window + counter

from collections import Counter

def min_window_substring(s: str, t: str) -> str:
    """Shortest substring of s that contains all characters of t."""
    if not t or not s:
        return ""
    
    target = Counter(t)
    have = {}
    
    needed = len(target)
    formed = 0  # how many distinct chars meet target count
    
    left = 0
    best_len = float("inf")
    best_range = (0, 0)
    
    for right, ch in enumerate(s):
        have[ch] = have.get(ch, 0) + 1
        if ch in target and have[ch] == target[ch]:
            formed += 1
        
        # Try to shrink from the left
        while formed == needed:
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_range = (left, right)
            
            have[s[left]] -= 1
            if s[left] in target and have[s[left]] < target[s[left]]:
                formed -= 1
            left += 1
    
    return s[best_range[0]:best_range[1] + 1] if best_len < float("inf") else ""

Problem: longest repeating character replacement

Given a string and k allowed replacements, longest substring where one character can dominate:

def longest_repeat_replacement(s: str, k: int) -> int:
    count = {}
    left = 0
    max_count = 0
    best = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        max_count = max(max_count, count[ch])
        # Window valid if: window_size - max_count <= k
        if (right - left + 1) - max_count > k:
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Trick: we don’t need to update max_count when shrinking — the window only grows or stays the same, so a stale max_count still gives a valid (potentially larger) answer.

Pitfalls

  • Forgetting to update aggregate when shrinking AND when growing.
  • Using a set instead of a counter when the same character can appear multiple times.
  • Off-by-one in right - left + 1 (inclusive window length).
  • Recomputing the window state from scratch — defeats the O(n) goal.

Interview angle

  • “When is a sliding window the right pattern?” - contiguous subarray or substring problems asking for a longest, shortest, or count meeting a condition. Non-contiguous requirements are usually dynamic programming instead.
  • “Fixed or variable window?” - fixed when the size is given (average of every k-length window); variable when the size is determined by a condition, where you expand the right edge and contract the left while the condition is violated.
  • “Why is it linear despite the inner loop?” - amortised: each index enters the window once and leaves once, so total pointer movement is bounded by 2n regardless of how the inner while behaves on any single iteration.
  • “Longest substring without repeating characters?” - the canonical variable window: a set or last-seen map, expand right, and move left past the previous occurrence when a duplicate appears.
Previous
Two pointers