Sliding Window Pattern¶

def max_sum_subarray(arr: list[int], k: int) -> int:
    """Maximum sum of any subarray of length k."""
    if len(arr) < k:
        return -1

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

    # Slide window: add one element, remove one element
    for i in range(k, len(arr)):
        window_sum += arr[i]       # add new right element
        window_sum -= arr[i - k]   # remove old left element
        max_sum = max(max_sum, window_sum)

    return max_sum  # O(n) time, O(1) space

# Test
print(max_sum_subarray([3, 1, 2, 5, 8, 2, 6, 1, 4, 9], 3))  # 16

def longest_subarray_with_sum_le_k(arr: list[int], k: int) -> int:
    """Longest contiguous subarray with sum ≤ k.
    Assumes non-negative arr — shrinking from the left is only safe then
    (a negative could make the sum smaller, so you might need a different algorithm)."""
    left = 0
    current_sum = 0
    max_length = 0

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

        # Shrink window until constraint satisfied
        while current_sum > k:
            current_sum -= arr[left]
            left += 1

        # Window [left..right] satisfies constraint
        max_length = max(max_length, right - left + 1)

    return max_length  # O(n) — each element enters/exits window once

def length_of_longest_substring(s: str) -> int:
    """
    Pattern: Variable window — shrink when duplicate found
    Clue: "longest substring" + "without repeating" → sliding window
    """
    char_index = {}  # char → last seen index
    left = 0
    max_len = 0

    for right, char in enumerate(s):
        # If char seen and within current window
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1  # skip past duplicate

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

    return max_len

# "abcabcbb" → 3 ("abc")
# "pwwkew"   → 3 ("wke")
# Time: O(n), Space: O(min(m,n)) where m=charset size

def min_window(s: str, t: str) -> str:
    """
    Find the smallest window in s containing all chars of t.
    Pattern: Variable window with character frequency tracking
    """
    from collections import Counter

    need = Counter(t)
    have = {}
    formed = 0     # how many chars satisfy the required frequency
    required = len(need)  # how many unique chars need to be satisfied
    left = 0
    min_len = float('inf')
    result = ""

    for right, char in enumerate(s):
        have[char] = have.get(char, 0) + 1
        if char in need and have[char] == need[char]:
            formed += 1

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

            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 result  # O(s + t) time, O(s + t) space

def max_score(card_points: list[int], k: int) -> int:
    """
    Pick k cards from left or right end of array.
    Insight: picking k from ends = leaving n-k in the middle.
    Find minimum sum window of size n-k, answer = total - min_window.
    """
    n = len(card_points)
    window_size = n - k
    total = sum(card_points)

    if window_size == 0:
        return total

    window_sum = sum(card_points[:window_size])
    min_window = window_sum

    for i in range(window_size, n):
        window_sum += card_points[i] - card_points[i - window_size]
        min_window = min(min_window, window_sum)

    return total - min_window

def sliding_window_template(arr, constraint):
    left = 0
    state = initial_state()  # e.g., Counter(), sum, set
    result = initial_result()

    for right in range(len(arr)):
        update_state(arr[right], state)  # add arr[right]

        while not constraint(state):     # window violates constraint
            undo_state(arr[left], state) # remove arr[left]
            left += 1

        result = update_result(result, left, right)

    return result

# Always check:
# 1. Empty array/string
# 2. k > len(arr) (fixed window)
# 3. All same characters
# 4. Window never satisfies constraint (return 0 or "")
# 5. Answer is entire array

def robust_max_sum(arr, k):
    if not arr or k > len(arr) or k <= 0:
        return 0  # or raise ValueError
    # ... rest of solution