Sliding Window Technique — Deep Dive

Solve advanced sliding window problems — minimum window substring, sliding window maximum with deque, and string permutation matching in Python.

Advanced sliding window patterns

The basic sliding window handles sums and simple conditions. Advanced problems require more sophisticated window state: hash maps for character counts, deques for monotonic structures, and multiple windows for complex constraints.

Pattern 1: Window with character frequency map

Minimum Window Substring

Given strings s and t, find the minimum window in s that contains all characters of t.

from collections import Counter

def min_window(s, t):
    if not t or not s:
        return ""

    target = Counter(t)
    required = len(target)  # unique chars needed
    formed = 0              # unique chars satisfied

    window_counts = {}
    left = 0
    best = (float('inf'), 0, 0)  # (length, left, right)

    for right, char in enumerate(s):
        window_counts[char] = window_counts.get(char, 0) + 1

        if char in target and window_counts[char] == target[char]:
            formed += 1

        while formed == required:
            length = right - left + 1
            if length < best[0]:
                best = (length, left, right)

            # Shrink from left
            left_char = s[left]
            window_counts[left_char] -= 1
            if left_char in target and window_counts[left_char] < target[left_char]:
                formed -= 1
            left += 1

    return "" if best[0] == float('inf') else s[best[1]:best[2] + 1]

print(min_window("ADOBECODEBANC", "ABC"))  # "BANC"

Time: O(|s| + |t|). Space: O(|s| + |t|).

The formed counter is the critical optimization. Instead of comparing full frequency maps each iteration (O(26) or O(128)), we track how many unique characters have reached their required count. This makes the inner check O(1).

Longest Substring with At Most K Distinct Characters

def longest_k_distinct(s, k):
    if k == 0:
        return 0

    counts = {}
    left = 0
    best = 0

    for right, char in enumerate(s):
        counts[char] = counts.get(char, 0) + 1

        while len(counts) > k:
            left_char = s[left]
            counts[left_char] -= 1
            if counts[left_char] == 0:
                del counts[left_char]
            left += 1

        best = max(best, right - left + 1)

    return best

print(longest_k_distinct("eceba", 2))   # 3 ("ece")
print(longest_k_distinct("araaci", 2))  # 4 ("araa")

Pattern 2: Sliding window maximum with deque

Finding the maximum in every window of size k seems like it requires O(k) per window (O(nk) total). A monotonic deque achieves O(n).

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # stores indices, front is always max
    result = []

    for i, num in enumerate(nums):
        # Remove elements outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove smaller elements (they can never be the max)
        while dq and nums[dq[-1]] < num:
            dq.pop()

        dq.append(i)

        # Window is fully formed
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

Time: O(n) — each element enters and leaves the deque at most once. Space: O(k) for the deque.

Why monotonic deque works: The deque maintains indices in decreasing order of their values. When a new element arrives that is larger than the back of the deque, the smaller elements are removed — they can never be the maximum of any future window because the new element is both larger and newer.

Sliding window minimum

Same structure, just reverse the comparison:

def min_sliding_window(nums, k):
    dq = deque()
    result = []

    for i, num in enumerate(nums):
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        while dq and nums[dq[-1]] > num:  # changed > to maintain ascending
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

Pattern 3: String permutation / anagram matching

Check if s2 contains a permutation of s1

from collections import Counter

def check_inclusion(s1, s2):
    if len(s1) > len(s2):
        return False

    target = Counter(s1)
    window = Counter(s2[:len(s1)])

    if window == target:
        return True

    for i in range(len(s1), len(s2)):
        # Add right character
        window[s2[i]] += 1
        # Remove left character
        left_char = s2[i - len(s1)]
        window[left_char] -= 1
        if window[left_char] == 0:
            del window[left_char]

        if window == target:
            return True

    return False

print(check_inclusion("ab", "eidbaooo"))  # True ("ba" is permutation)

Optimization: Comparing Counter objects is O(26) for lowercase ASCII. For tighter performance, track the number of matching characters:

def check_inclusion_optimized(s1, s2):
    if len(s1) > len(s2):
        return False

    target = [0] * 26
    window = [0] * 26

    for c in s1:
        target[ord(c) - ord('a')] += 1
    for c in s2[:len(s1)]:
        window[ord(c) - ord('a')] += 1

    matches = sum(1 for i in range(26) if target[i] == window[i])

    for i in range(len(s1), len(s2)):
        if matches == 26:
            return True

        # Add right
        idx = ord(s2[i]) - ord('a')
        window[idx] += 1
        if window[idx] == target[idx]:
            matches += 1
        elif window[idx] == target[idx] + 1:
            matches -= 1

        # Remove left
        idx = ord(s2[i - len(s1)]) - ord('a')
        window[idx] -= 1
        if window[idx] == target[idx]:
            matches += 1
        elif window[idx] == target[idx] - 1:
            matches -= 1

    return matches == 26

print(check_inclusion_optimized("ab", "eidbaooo"))  # True

This makes each step truly O(1) — no counter comparison needed.

Pattern 4: Counting subarrays with a condition

Subarrays with at most K distinct elements

To count subarrays with exactly K distinct elements, use the identity: exactly_k = at_most_k - at_most_(k-1).

def subarrays_with_k_distinct(nums, k):
    def at_most(k):
        counts = {}
        left = 0
        result = 0
        for right, num in enumerate(nums):
            counts[num] = counts.get(num, 0) + 1
            while len(counts) > k:
                left_num = nums[left]
                counts[left_num] -= 1
                if counts[left_num] == 0:
                    del counts[left_num]
                left += 1
            result += right - left + 1  # all subarrays ending at right
        return result

    return at_most(k) - at_most(k - 1)

print(subarrays_with_k_distinct([1, 2, 1, 2, 3], 2))  # 7

Key insight: right - left + 1 counts all valid subarrays ending at right. The window [left, right] is valid, and so are [left+1, right], [left+2, right], etc. — all subarrays starting between left and right that end at right.

Pattern 5: Multiple conditions with two maps

Longest Repeating Character Replacement

Given a string, replace at most k characters to get the longest substring of identical characters.

def character_replacement(s, k):
    counts = {}
    left = 0
    max_freq = 0
    best = 0

    for right, char in enumerate(s):
        counts[char] = counts.get(char, 0) + 1
        max_freq = max(max_freq, counts[char])

        # Window is invalid if replacements needed > k
        window_len = right - left + 1
        if window_len - max_freq > k:
            counts[s[left]] -= 1
            left += 1

        best = max(best, right - left + 1)

    return best

print(character_replacement("AABABBA", 1))  # 4 ("AABA"→"AAAA")

Subtle optimization: max_freq is never decreased. This is correct because we only care about max_freq increasing (which could produce a longer valid window). If max_freq stays the same or decreases, the window cannot grow, so we just slide it forward without shrinking.

Performance comparison

Benchmarking sliding window vs brute force for “maximum sum subarray of size k”:

import timeit

def brute_force(nums, k):
    return max(sum(nums[i:i+k]) for i in range(len(nums) - k + 1))

def sliding_window(nums, k):
    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

import random
nums = [random.randint(1, 100) for _ in range(100_000)]
k = 1000

# Brute force: O(n*k) ≈ 10^8 operations
# Sliding window: O(n) ≈ 10^5 operations

For n=100,000 and k=1,000: brute force takes ~3 seconds, sliding window takes ~15 milliseconds. That is a 200× speedup that grows with k.

Edge cases to handle

  1. Empty input: Return 0 or empty string.
  2. Window larger than array: Return the full array or handle gracefully.
  3. All elements identical: Window expands to full length.
  4. Single element: Window of size 1.
  5. Negative numbers: Sliding window for max sum still works; for min sum, adjust the comparison.
def safe_sliding_window(nums, k):
    if not nums or k <= 0 or k > len(nums):
        return 0
    # ... normal implementation

One thing to remember: Every sliding window problem boils down to: what enters the window, what leaves the window, and how do you maintain the window state efficiently. The deque handles order-dependent queries (max/min). The hash map handles frequency-dependent queries (distinct count, anagram). Choose the right state structure and the rest follows.

pythonalgorithmssliding-windowinterviews

See Also

Related Topics

ab-testing How tech companies run thousands of experiments at once to improve their products — the scientific method applied to everything from button colors to recommendation algorithms. 3 levels → activation-functions Why neural networks need these tiny mathematical functions — and how ReLU's simplicity accidentally made deep learning possible. 3 levels → ai-agents-architecture How AI systems go from answering questions to actually doing things — the design patterns that turn language models into autonomous agents that browse, code, and plan. 3 levels →