Dynamic Sliding Window

Expand right until invalid, shrink left until valid — the universal approach for variable-size window problems.

9 min readLeetCode Patterns for InterviewsCode

The Pattern

Dynamic windows grow from the right and shrink from the left. The window always maintains a valid state (or we measure its invalid state for maximum tracking). Expand right, check condition, if violated shrink left.

Dynamic window template


def max_window(s: str, k: int) -> int:
    """Maximum window with at most k distinct characters."""
    freq = {}
    l, best = 0, 0
    for r in range(len(s)):
        freq[s[r]] = freq.get(s[r], 0) + 1  # expand
        # Shrink while invalid (more than k distinct chars)
        while len(freq) > k:
            freq[s[l]] -= 1
            if freq[s[l]] == 0:
                del freq[s[l]]
            l += 1
        # Window [l..r] is valid
        best = max(best, r - l + 1)
    return best

# Usage
print(max_window("eceba", 2))  # 3 ("ece")

The invariant: after the inner while loop, the window [l..r] always satisfies the constraint. We measure/record after ensuring validity.

Template

Shrink condition vs measure timing

For 'maximum valid window': shrink until valid, then measure. For 'minimum window containing all': measure when valid, then shrink to find smaller. The difference is whether you measure before or after shrinking.

Problems

#3Longest Substring Without Repeating CharactersMediumDynamic window with set · O(n) time · O(min(n, alphabet)) space #76Minimum Window SubstringHardDynamic window — minimum covering all chars · O(n + m) time · O(n + m) space #424Longest Repeating Character ReplacementMediumDynamic window — count majority char · O(n) time · O(1) space #209Minimum Size Subarray SumMediumDynamic window minimum · O(n) time · O(1) space

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.