Variable-Size Window Problems

Variable-size windows expand and shrink based on certain conditions. These are often "longest" or "shortest" subarray/substring problems.

Pattern Recognition

Variable window problems often ask:

• "Longest substring/subarray with..."
• "Shortest substring/subarray with..."
• "At most k..." or "At least k..."
• "Contains all..." or "No repeating..."

The Template

def variable_window_template(arr, condition):
    left = 0
    window_state = initialize()
    result = initialize_result()  # max, min, count, etc.

    for right in range(len(arr)):
        # Expand window - add right element
        add_to_window(window_state, arr[right])

        # Shrink window while invalid
        while not is_valid(window_state, condition):
            remove_from_window(window_state, arr[left])
            left += 1

        # Update result with current valid window
        result = update_result(result, right - left + 1)

    return result

Problem 1: Longest Substring Without Repeating

Problem: Find length of longest substring without repeating characters.

def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        # Shrink until no duplicates
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1

        # Add current char
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len

print(length_of_longest_substring("abcabcbb"))  # 3 ("abc")
print(length_of_longest_substring("pwwkew"))    # 3 ("wke")

Time: O(n), Space: O(min(n, alphabet size))

Problem 2: Longest Substring with K Distinct

Problem: Find longest substring with at most k distinct characters.

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

    char_freq = {}
    left = 0
    max_len = 0

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

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

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

    return max_len

print(longest_substring_k_distinct("eceba", 2))    # 3 ("ece")
print(longest_substring_k_distinct("aa", 1))       # 2 ("aa")

Problem 3: Minimum Window Substring

Problem: Find minimum window in s containing all characters of t.

from collections import Counter

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

    required = Counter(t)
    needed = len(required)
    formed = 0

    window_counts = {}
    left = 0
    min_len = float('inf')
    result = ""

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

        # Check if requirement satisfied
        if char in required and window_counts[char] == required[char]:
            formed += 1

        # Try to shrink
        while formed == needed and left <= right:
            # Update result
            if right - left + 1 < min_len:
                min_len = right - left + 1
                result = s[left:right + 1]

            # Remove left char
            left_char = s[left]
            window_counts[left_char] -= 1
            if left_char in required and window_counts[left_char] < required[left_char]:
                formed -= 1
            left += 1

    return result

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

Key: Expand to make valid, shrink to find minimum.

Problem 4: Max Consecutive Ones III

Problem: Max length of contiguous 1s if you can flip at most k zeros.

def longest_ones(nums, k):
    left = 0
    zeros = 0
    max_len = 0

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

        # Shrink if too many zeros
        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1

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

    return max_len

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

Problem 5: Longest Repeating Character Replacement

Problem: Find longest substring with same letter after replacing at most k characters.

def character_replacement(s, k):
    char_freq = {}
    left = 0
    max_freq = 0
    max_len = 0

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

        # Window size - max frequency = replacements needed
        window_size = right - left + 1

        # If too many replacements needed, shrink
        if window_size - max_freq > k:
            left_char = s[left]
            char_freq[left_char] -= 1
            left += 1

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

    return max_len

print(character_replacement("ABAB", 2))    # 4 (all same)
print(character_replacement("AABABBA", 1)) # 4 ("AABA" or "ABBA")

Key Insight: window_size - max_frequency = changes needed

Problem 6: Fruits Into Baskets

Problem: Pick maximum fruits with at most 2 types.

def total_fruit(fruits):
    """Longest subarray with at most 2 distinct elements"""
    fruit_freq = {}
    left = 0
    max_fruits = 0

    for right in range(len(fruits)):
        # Add fruit
        fruit = fruits[right]
        fruit_freq[fruit] = fruit_freq.get(fruit, 0) + 1

        # Shrink if too many types
        while len(fruit_freq) > 2:
            left_fruit = fruits[left]
            fruit_freq[left_fruit] -= 1
            if fruit_freq[left_fruit] == 0:
                del fruit_freq[left_fruit]
            left += 1

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

    return max_fruits

print(total_fruit([1,2,1]))       # 3
print(total_fruit([0,1,2,2]))     # 3 ([1,2,2])
print(total_fruit([1,2,3,2,2]))   # 4 ([2,3,2,2])

Problem 7: Subarrays with K Different Integers

Problem: Count subarrays with exactly k distinct integers.

def subarrays_with_k_distinct(nums, k):
    """Helper: at most k distinct"""
    def at_most_k(k):
        freq = {}
        left = 0
        count = 0

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

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

            # All subarrays ending at right
            count += right - left + 1

        return count

    # Exactly k = (at most k) - (at most k-1)
    return at_most_k(k) - at_most_k(k - 1)

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

Key Trick: Exactly k = At most k - At most (k-1)

Problem 8: Minimum Size Subarray Sum

Problem: Find minimum length subarray with sum ≥ target.

def min_subarray_len(target, nums):
    left = 0
    current_sum = 0
    min_len = float('inf')

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

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

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

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

Tips for Variable Window

1. Expand first: Always add right element
2. Then shrink: Use while loop to shrink until valid
3. Update result: After shrinking, window is valid
4. Track window state: Use hash map, set, or counters
5. Handle edge cases: Empty array, impossible target