Sliding Window Pattern

# Template A: FIXED window of size K. Slide one step at a time.
def fixed_window(arr, k):
    # Initialize: compute aggregate over the FIRST window of size K
    window_sum = sum(arr[:k])     # could also be a Counter for character problems
    best = window_sum             # track the optimal seen so far

    # Slide: for each new right boundary, update by adding the entering element
    # and removing the exiting element. O(1) per step instead of O(k).
    for right in range(k, len(arr)):
        window_sum += arr[right] - arr[right - k]   # add entering, remove exiting
        best = max(best, window_sum)
    return best


# Template B: VARIABLE window, MAXIMIZE valid window length.
# Use when problem says "longest [thing] with [constraint]".
# Shrink WHILE the window is INVALID. Update result AFTER the shrink loop.
def max_variable_window(arr, k):
    from collections import defaultdict
    left = 0
    state = defaultdict(int)               # whatever bookkeeping the constraint needs
    best = 0

    for right in range(len(arr)):
        state[arr[right]] += 1              # expand: add the entering element

        while len(state) > k:               # invariant violated -> shrink from the left
            state[arr[left]] -= 1
            if state[arr[left]] == 0:
                del state[arr[left]]        # CRUCIAL: drop zero-count keys for accurate distinct count
            left += 1

        # When we exit the while, the window is valid. Update the best length.
        best = max(best, right - left + 1)
    return best


# Template C: VARIABLE window, MINIMIZE valid window length.
# Use when problem says "shortest [thing] with [constraint]" (LC 209, LC 76).
# Shrink WHILE the window is VALID. Update result INSIDE the shrink loop.
def min_variable_window(arr, target):
    left = 0
    current = 0
    best = float('inf')

    for right in range(len(arr)):
        current += arr[right]               # expand

        while current >= target:            # window is VALID -> shrink to find a smaller one
            best = min(best, right - left + 1)   # record before shrinking, every valid size counts
            current -= arr[left]
            left += 1
            # loop continues -- window may still be valid even after one shrink

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

def max_sum_subarray_k(arr, k):
    """Find maximum sum of any contiguous subarray of size k.
    
    Example: arr = [2, 1, 5, 1, 3, 2], k = 3
      Window [2,1,5] sum=8, [1,5,1] sum=7, [5,1,3] sum=9, [1,3,2] sum=6
      Maximum sum = 9
    """
    if len(arr) < k:
        return -1
    
    # Initialize: compute the sum of the first window
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide: add the new element entering the window, remove the one leaving
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]  # O(1) update instead of recalculating
        max_sum = max(max_sum, window_sum)
    
    return max_sum

def min_subarray_sum(arr, target):
    """Find the shortest contiguous subarray with sum >= target.
    Return 0 if no such subarray exists.
    
    Example: arr = [2, 3, 1, 2, 4, 3], target = 7
      Window [2,3,1,2] sum=8 >= 7, length=4 -> shrink
      Window [3,1,2] sum=6 < 7 -> expand
      Window [3,1,2,4] sum=10 >= 7, length=4 -> shrink
      Window [1,2,4] sum=7 >= 7, length=3 -> shrink
      ...eventually find [4,3] sum=7 >= 7, length=2
    Answer: 2
    """
    left = 0
    current_sum = 0
    min_length = float('inf')
    
    for right in range(len(arr)):
        current_sum += arr[right]       # Expand: add new element
        
        while current_sum >= target:    # Shrink while the window is valid
            min_length = min(min_length, right - left + 1)
            current_sum -= arr[left]    # Remove leftmost element
            left += 1
    
    return min_length if min_length != float('inf') else 0

def longest_substring_k_unique(s, k):
    """Longest substring with exactly k unique characters"""
    from collections import defaultdict
    
    if k == 0:
        return 0
    
    left = 0
    char_count = defaultdict(int)
    max_length = 0
    
    for right in range(len(s)):
        char_count[s[right]] += 1
        
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
        
        if len(char_count) == k:
            max_length = max(max_length, right - left + 1)
    
    return max_length

# Template 1: Fixed Window
def fixed_window_template(arr, k):
    # Initialize first window
    window_result = sum(arr[:k])
    best = window_result
    
    for i in range(k, len(arr)):
        # Slide: remove arr[i-k], add arr[i]
        window_result = window_result - arr[i-k] + arr[i]
        best = max(best, window_result)
    
    return best

# Template 2: Variable Window (At Most K Pattern)
def variable_window_template(arr, k):
    left = 0
    count = {}
    result = 0
    
    for right in range(len(arr)):
        # Expand: add arr[right] to state
        count[arr[right]] = count.get(arr[right], 0) + 1
        
        # Shrink while invalid
        while len(count) > k:
            count[arr[left]] -= 1
            if count[arr[left]] == 0:
                del count[arr[left]]
            left += 1
        
        # Update result
        result = max(result, right - left + 1)
    
    return result

# Template 3: Minimum Window (Find Smallest Valid)
def min_window_template(arr, target):
    left = 0
    current_sum = 0
    min_length = float('inf')
    
    for right in range(len(arr)):
        current_sum += arr[right]
        
        while current_sum >= target:  # While window is valid
            min_length = min(min_length, right - left + 1)
            current_sum -= arr[left]
            left += 1
    
    return min_length if min_length != float('inf') else 0

from collections import defaultdict

def subarrays_exactly_k_distinct(arr, k):
    """Count subarrays with exactly k distinct elements"""
    def at_most_k(arr, k):
        left = 0
        count = defaultdict(int)
        result = 0
        
        for right in range(len(arr)):
            count[arr[right]] += 1
            
            while len(count) > k:
                count[arr[left]] -= 1
                if count[arr[left]] == 0:
                    del count[arr[left]]
                left += 1
            
            result += right - left + 1
        
        return result
    
    return at_most_k(arr, k) - at_most_k(arr, k - 1)