Intermediate

Variable Size Window

In variable-size window problems, you do not know the window size in advance. You expand the window by moving right and shrink it by moving left until the window satisfies (or violates) a condition. The answer is usually the minimum or maximum valid window.

💡

Variable Window Template: Expand right to grow the window. When the window becomes invalid (or valid, depending on the problem), shrink from the left. Track the best result at each step.

Problem 1: Minimum Window Substring (LeetCode 76)

Problem: Given strings s and t, find the minimum window in s that contains all characters of t (including duplicates).

Example: s = "ADOBECODEBANC", t = "ABC" → "BANC"

from collections import Counter

def min_window(s: str, t: str) -> str:
    """Find minimum window substring containing all characters of t.

    Time: O(|s| + |t|), Space: O(|s| + |t|)
    """
    if not t or not s:
        return ""

    need = Counter(t)
    have = {}
    formed = 0          # number of unique chars in t that are satisfied
    required = len(need) # number of unique chars in t

    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 this char's frequency requirement is met
        if char in need and have[char] == need[char]:
            formed += 1

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

            # Remove left char and shrink
            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]


# Test
assert min_window("ADOBECODEBANC", "ABC") == "BANC"
assert min_window("a", "a") == "a"
assert min_window("a", "aa") == ""
print("All tests passed!")

Problem 2: Longest Substring Without Repeating Characters (LeetCode 3)

Problem: Given a string s, find the length of the longest substring without repeating characters.

Example: s = "abcabcbb" → 3 ("abc")

def length_of_longest_substring(s: str) -> int:
    """Find length of longest substring without repeating characters.

    Time: O(n), Space: O(min(n, 26)) for lowercase or O(min(n, 128)) for ASCII
    """
    char_index = {}  # last seen index of each character
    left = 0
    max_len = 0

    for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            # Jump left pointer past the duplicate
            left = char_index[s[right]] + 1

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

    return max_len


# Test
assert length_of_longest_substring("abcabcbb") == 3
assert length_of_longest_substring("bbbbb") == 1
assert length_of_longest_substring("pwwkew") == 3
assert length_of_longest_substring("") == 0
print("All tests passed!")

✅

Optimization: Instead of using a set and shrinking one step at a time, store the last index of each character and jump left directly past the duplicate. This avoids redundant iterations.

Problem 3: Longest Repeating Character Replacement (LeetCode 424)

Problem: Given a string s and an integer k, find the length of the longest substring where you can replace at most k characters to make all characters the same.

Example: s = "AABABBA", k = 1 → 4 ("AABA" → replace B with A)

def character_replacement(s: str, k: int) -> int:
    """Find longest substring after replacing at most k characters.

    Key insight: window is valid when (window_size - max_freq) <= k.
    Time: O(n), Space: O(26) = O(1)
    """
    count = {}
    left = 0
    max_freq = 0  # frequency of the most common char in current window
    max_len = 0

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

        # If replacements needed > k, shrink window
        # Replacements needed = window_size - max_freq
        window_size = right - left + 1
        if window_size - max_freq > k:
            count[s[left]] -= 1
            left += 1
        else:
            max_len = max(max_len, window_size)

    return max_len


# Test
assert character_replacement("ABAB", 2) == 4
assert character_replacement("AABABBA", 1) == 4
print("All tests passed!")

Problem 4: Subarrays with K Different Integers (LeetCode 992)

Problem: Given an integer array nums and an integer k, return the number of subarrays with exactly k distinct integers.

Example: nums = [1,2,1,2,3], k = 2 → 7

def subarrays_with_k_distinct(nums: list[int], k: int) -> int:
    """Count subarrays with exactly k distinct integers.

    Trick: exactly(k) = at_most(k) - at_most(k-1)
    Time: O(n), Space: O(k)
    """
    def at_most_k(nums, 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 at most k distinct
            result += right - left + 1

        return result

    return at_most_k(nums, k) - at_most_k(nums, k - 1)


# Test
assert subarrays_with_k_distinct([1, 2, 1, 2, 3], 2) == 7
assert subarrays_with_k_distinct([1, 2, 1, 3, 4], 3) == 3
print("All tests passed!")

✅

Key Pattern: "Exactly K" problems are almost always solved as at_most(k) - at_most(k-1). This transforms a hard constraint into two easy sliding window passes.

Problem 5: Minimum Size Subarray Sum (LeetCode 209)

Problem: Given an array of positive integers and a target, find the minimal length of a contiguous subarray whose sum is greater than or equal to target.

Example: nums = [2,3,1,2,4,3], target = 7 → 2 (subarray [4,3])

def min_subarray_len(target: int, nums: list[int]) -> int:
    """Find minimal length subarray with sum >= target.

    Time: O(n), Space: O(1)
    """
    left = 0
    current_sum = 0
    min_len = float('inf')

    for right in range(len(nums)):
        current_sum += nums[right]

        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= nums[left]
            left += 1

    return 0 if min_len == float('inf') else min_len


# Test
assert min_subarray_len(7, [2, 3, 1, 2, 4, 3]) == 2
assert min_subarray_len(4, [1, 4, 4]) == 1
assert min_subarray_len(11, [1, 1, 1, 1, 1, 1, 1, 1]) == 0
print("All tests passed!")

Problem 6: Longest Substring with At Most K Distinct Characters (LeetCode 340)

Problem: Given a string s and an integer k, return the length of the longest substring that contains at most k distinct characters.

Example: s = "eceba", k = 2 → 3 ("ece")

def longest_k_distinct(s: str, k: int) -> int:
    """Find longest substring with at most k distinct characters.

    Time: O(n), Space: O(k)
    """
    if k == 0:
        return 0

    char_count = {}
    left = 0
    max_len = 0

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

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

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

    return max_len


# Test
assert longest_k_distinct("eceba", 2) == 3
assert longest_k_distinct("aa", 1) == 2
assert longest_k_distinct("a", 0) == 0
print("All tests passed!")

Summary

Problem	Time	Space	Key Technique
Minimum Window Substring	O(n)	O(n)	Two counters + formed count
Longest Substring No Repeats	O(n)	O(min(n,26))	Last-seen index map
Longest Repeating Replacement	O(n)	O(1)	Max frequency tracking
Subarrays K Distinct	O(n)	O(k)	at_most(k) - at_most(k-1)
Minimum Size Subarray Sum	O(n)	O(1)	Shrink when sum ≥ target
Longest K Distinct Chars	O(n)	O(k)	Frequency map + shrink

← Previous Fixed Size Window Next → Two Pointers Basic