Sliding Window: Advanced Patterns and Templates

The sliding window technique maintains a “window” (contiguous subarray or substring) that slides over the input. Instead of recalculating from scratch for every position, you add one element to the right and remove one from the left, keeping the computation incremental and efficient.

This turns O(n * k) or O(n^2) brute-force solutions into O(n).

Fixed-size window template

When the window size is given as a constant k, the structure is straightforward:

def fixed_window_template(arr, k):
    """
    Template for fixed-size window of size k.
    Time: O(n), Space: O(1) or O(k) depending on problem
    """
    n = len(arr)
    if n < k:
        return None

    # Initialize window with first k elements
    window_sum = sum(arr[:k])
    best = window_sum

    # Slide window: add right element, remove left element
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        best = max(best, window_sum)  # or min, or whatever

    return best

Maximum sum subarray of size K

def max_sum_subarray(arr, k):
    """
    Find the maximum sum of any contiguous subarray of size k.
    Time: O(n), Space: O(1)
    """
    if len(arr) < k:
        return 0

    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum


print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))  # 9 (5 + 1 + 3)
print(max_sum_subarray([2, 3, 4, 1, 5], 2))      # 7 (3 + 4)

Maximum of all subarrays of size K (using deque)

from collections import deque

def max_of_subarrays(arr, k):
    """
    Find the maximum element in every window of size k.
    Uses a monotonic deque.
    Time: O(n), Space: O(k)
    """
    result = []
    dq = deque()  # Stores indices, values in decreasing order

    for i in range(len(arr)):
        # Remove elements outside the window
        while dq and dq[0] <= i - k:
            dq.popleft()

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

        dq.append(i)

        # Window is complete starting from index k-1
        if i >= k - 1:
            result.append(arr[dq[0]])

    return result


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

Find all anagrams in a string

from collections import Counter

def find_anagrams(s, p):
    """
    Find all start indices where anagram of p begins in s.
    Fixed window of size len(p).
    Time: O(n), Space: O(1) - at most 26 characters
    """
    if len(p) > len(s):
        return []

    p_count = Counter(p)
    window = Counter(s[:len(p)])
    result = []

    if window == p_count:
        result.append(0)

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

        if window == p_count:
            result.append(i - len(p) + 1)

    return result


print(find_anagrams("cbaebabacd", "abc"))  # [0, 6]
print(find_anagrams("abab", "ab"))          # [0, 1, 2]

Variable-size window template

When the window size is not fixed, you expand the right boundary and shrink the left boundary based on some condition.

def variable_window_template(arr):
    """
    Template for variable-size window.
    Time: O(n) - each element is added and removed at most once
    """
    left = 0
    window_state = {}  # frequency map, sum, etc.
    best = 0  # or float('inf') for minimization

    for right in range(len(arr)):
        # Expand: add arr[right] to window state
        update_state_add(window_state, arr[right])

        # Shrink: while window is invalid, remove from left
        while window_is_invalid(window_state):
            update_state_remove(window_state, arr[left])
            left += 1

        # Update answer
        best = max(best, right - left + 1)

    return best

Why this is O(n): The right pointer moves n times. The left pointer also moves at most n times total across all iterations (it never moves backward). So the total work is O(2n) = O(n).

Longest substring without repeating characters

def length_of_longest_substring(s):
    """
    LeetCode 3: Longest substring without repeating characters.
    Time: O(n), Space: O(min(n, 26))
    """
    char_index = {}  # Last seen index of each character
    left = 0
    max_length = 0

    for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            left = char_index[s[right]] + 1

        char_index[s[right]] = right
        max_length = max(max_length, right - left + 1)

    return max_length


print(length_of_longest_substring("abcabcbb"))  # 3 ("abc")
print(length_of_longest_substring("bbbbb"))      # 1 ("b")
print(length_of_longest_substring("pwwkew"))     # 3 ("wke")

Longest substring with at most K distinct characters

def longest_k_distinct(s, k):
    """
    Longest substring with at most k distinct characters.
    Time: O(n), Space: O(k)
    """
    if k == 0:
        return 0

    char_count = {}
    left = 0
    max_length = 0

    for right in range(len(s)):
        # Expand: add character
        char_count[s[right]] = char_count.get(s[right], 0) + 1

        # Shrink: too many distinct characters
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1

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

    return max_length


print(longest_k_distinct("eceba", 2))     # 3 ("ece")
print(longest_k_distinct("aa", 1))         # 2 ("aa")
print(longest_k_distinct("aabacbebebe", 3))  # 7 ("cbebebe")

Minimum window substring

This is the classic hard sliding window problem. Find the smallest window in s that contains all characters of t.

from collections import Counter

def min_window(s, t):
    """
    LeetCode 76: Minimum window substring.
    Time: O(n), Space: O(m) where m = len(t)
    """
    if not t or not s:
        return ""

    need = Counter(t)
    have = {}
    formed = 0       # Characters with correct frequency
    required = len(need)  # Distinct characters needed

    left = 0
    min_len = float('inf')
    min_start = 0

    for right in range(len(s)):
        char = s[right]
        have[char] = have.get(char, 0) + 1

        # Check if current character's frequency matches required
        if char in need and have[char] == need[char]:
            formed += 1

        # Try to shrink the window
        while formed == required:
            # Update minimum
            window_len = right - left + 1
            if window_len < min_len:
                min_len = window_len
                min_start = left

            # Remove left character
            left_char = s[left]
            have[left_char] -= 1
            if left_char in need and have[left_char] < need[left_char]:
                formed -= 1
            left += 1

    return "" if min_len == float('inf') else s[min_start:min_start + min_len]


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

Step-by-step for “ADOBECODEBANC”, “ABC”:

1. Expand right until window contains A, B, and C.
2. First valid window: “ADOBEC” (indices 0-5).
3. Shrink from left: remove A, window becomes “DOBEC” - missing A.
4. Expand right again to find next A.
5. Eventually find “BANC” (indices 9-12) which is shorter.

Longest repeating character replacement

def character_replacement(s, k):
    """
    LeetCode 424: Longest substring with at most k replacements.
    Time: O(n), Space: O(26) = O(1)
    """
    count = {}
    left = 0
    max_freq = 0  # Frequency of most common char in window
    max_length = 0

    for right in range(len(s)):
        count[s[right]] = count.get(s[right], 0) + 1
        max_freq = max(max_freq, count[s[right]])

        # Window size - most frequent char count = chars to replace
        # If this exceeds k, shrink
        window_size = right - left + 1
        if window_size - max_freq > k:
            count[s[left]] -= 1
            left += 1

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

    return max_length


print(character_replacement("ABAB", 2))     # 4 ("AAAA" or "BBBB")
print(character_replacement("AABABBA", 1))  # 4 ("AABA" -> "AAAA")

Count subarrays with at most K distinct elements

def subarrays_at_most_k_distinct(nums, k):
    """
    Count subarrays with at most k distinct elements.
    Time: O(n), Space: O(k)
    """
    count = {}
    left = 0
    result = 0

    for right in range(len(nums)):
        count[nums[right]] = count.get(nums[right], 0) + 1

        while len(count) > k:
            count[nums[left]] -= 1
            if count[nums[left]] == 0:
                del count[nums[left]]
            left += 1

        # All subarrays ending at right with left boundary >= left
        result += right - left + 1

    return result


def subarrays_exactly_k_distinct(nums, k):
    """
    Count subarrays with exactly k distinct elements.
    Trick: exactly(k) = atMost(k) - atMost(k-1)
    Time: O(n), Space: O(k)
    """
    return (subarrays_at_most_k_distinct(nums, k) -
            subarrays_at_most_k_distinct(nums, k - 1))


print(subarrays_exactly_k_distinct([1, 2, 1, 2, 3], 2))  # 7
print(subarrays_exactly_k_distinct([1, 2, 1, 3, 4], 3))  # 3

The atMost trick: Counting subarrays with exactly K distinct elements is hard directly, but counting “at most K” is easy with sliding window. Then exactly(K) = atMost(K) - atMost(K-1).

Permutation in string

def check_inclusion(s1, s2):
    """
    Check if any permutation of s1 exists as a substring of s2.
    Time: O(n), Space: O(1)
    """
    if len(s1) > len(s2):
        return False

    s1_count = [0] * 26
    window = [0] * 26

    for c in s1:
        s1_count[ord(c) - ord('a')] += 1

    for i in range(len(s2)):
        window[ord(s2[i]) - ord('a')] += 1

        if i >= len(s1):
            window[ord(s2[i - len(s1)]) - ord('a')] -= 1

        if window == s1_count:
            return True

    return False


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

Maximum consecutive ones with at most K flips

def longest_ones(nums, k):
    """
    LeetCode 1004: Max consecutive ones III.
    Sliding window where we allow at most k zeros in window.
    Time: O(n), Space: O(1)
    """
    left = 0
    zeros = 0
    max_length = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zeros += 1

        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1

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

    return max_length


print(longest_ones([1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], 2))  # 6
print(longest_ones([0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1], 3))  # 10

Sliding window vs two pointer

Feature	Sliding Window	Two Pointer
Direction	Both pointers move right	Pointers can move toward each other
Window	Maintains contiguous subarray	Not necessarily contiguous
State	Tracks window state (sum, count, map)	Usually minimal state
Use case	Subarray/substring problems	Sorted array, pair finding
Examples	Min window substring	Two sum (sorted), container

The boundary is blurry. Sliding window is technically a special case of two pointer where both pointers move in the same direction.

Common mistakes

Mistake 1: Forgetting to handle the initial window.

# WRONG: starts sliding before window is full
for i in range(len(arr)):
    window_sum += arr[i]
    window_sum -= arr[i - k]  # i - k can be negative!

# CORRECT: initialize first window, then slide
window_sum = sum(arr[:k])
for i in range(k, len(arr)):
    window_sum += arr[i] - arr[i - k]

Mistake 2: Not removing elements from the frequency map when their count reaches zero.

# WRONG: leaves zero-count entries
count[char] -= 1

# CORRECT: clean up
count[char] -= 1
if count[char] == 0:
    del count[char]

Mistake 3: Using while vs if for shrinking incorrectly.

For variable windows, use while to shrink until the window is valid again. Using if only shrinks once, which may not be enough.

Complexity summary

Problem	Time	Space
Max sum subarray of size K	O(n)	O(1)
Sliding window maximum	O(n)	O(k)
Longest substring no repeat	O(n)	O(min(n, 26))
Longest K distinct	O(n)	O(k)
Min window substring	O(n + m)	O(m)
Find all anagrams	O(n)	O(1)
Subarrays with K distinct	O(n)	O(k)

Practice problems

Problem	Type	Difficulty
Max Sum Subarray of Size K	Fixed	Easy
Longest Substring No Repeat (LC 3)	Variable	Medium
Min Window Substring (LC 76)	Variable	Hard
Find All Anagrams (LC 438)	Fixed	Medium
Permutation in String (LC 567)	Fixed	Medium
Longest Repeating Replacement (LC 424)	Variable	Medium
Max Consecutive Ones III (LC 1004)	Variable	Medium
Sliding Window Maximum (LC 239)	Fixed + Deque	Hard
Subarrays with K Distinct (LC 992)	Variable	Hard
Fruit Into Baskets (LC 904)	Variable (K=2)	Medium

Key takeaways

1. Fixed-size windows initialize with the first K elements, then add one and remove one per step.
2. Variable-size windows expand right and shrink left based on a validity condition. Both pointers move at most n times total.
3. The atMost trick converts “exactly K” problems into two “at most” calls: exactly(K) = atMost(K) - atMost(K-1).
4. Use a monotonic deque for sliding window maximum/minimum.
5. Always verify your window state is properly maintained when shrinking - clean up zero-count entries from frequency maps.