Sliding Window Patterns: Complete Reference¶

def sliding_window_template(sequence):
    """
    Generic sliding window template.

    Key components:
    1. State: Data structure tracking window contents
    2. Invariant: Condition that must hold for valid window
    3. Expand: Always move right pointer forward
    4. Contract: Move left pointer to restore invariant
    5. Update: Record answer when window is valid
    """
    state = initialize_state()
    left = 0
    answer = initial_answer()

    for right, element in enumerate(sequence):
        # EXPAND: Add element at right to window state
        update_state_add(state, element)

        # CONTRACT: Shrink window until invariant is restored
        while invariant_violated(state):
            update_state_remove(state, sequence[left])
            left += 1

        # UPDATE: Record answer for current valid window
        answer = update_answer(answer, left, right)

    return answer

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

    Algorithm:
    - Maintain a window where all characters are unique
    - Use a dictionary to track the last seen index of each character
    - When a duplicate is found, jump left pointer past the previous occurrence

    Time Complexity: O(n) - each character visited at most twice
    Space Complexity: O(min(n, σ)) - where σ is the alphabet size

    Args:
        s: Input string

    Returns:
        Length of the longest substring with all unique characters
    """
    # State: Map each character to its most recent index in the string
    last_seen_index: dict[str, int] = {}

    # Window boundaries
    left = 0
    max_length = 0

    for right, char in enumerate(s):
        # Check if character was seen within the current window
        # Key insight: We only care about occurrences at or after 'left'
        if char in last_seen_index and last_seen_index[char] >= left:
            # CONTRACT: Move left pointer past the previous occurrence
            # This single jump replaces the typical while-loop contraction
            left = last_seen_index[char] + 1

        # UPDATE: Record character's position for future duplicate detection
        last_seen_index[char] = right

        # UPDATE ANSWER: Current window [left, right] is valid
        # Window length = right - left + 1
        max_length = max(max_length, right - left + 1)

    return max_length

def length_of_longest_substring_k_distinct(s: str, k: int) -> int:
    """
    Find the length of the longest substring with at most K distinct characters.

    Algorithm:
    - Maintain a frequency map of characters in the current window
    - When distinct count exceeds K, shrink window from left until count ≤ K

    Time Complexity: O(n) - each character added and removed at most once
    Space Complexity: O(K) - at most K+1 entries in the frequency map

    Args:
        s: Input string
        k: Maximum number of distinct characters allowed

    Returns:
        Length of the longest valid substring
    """
    if k == 0:
        return 0

    # State: Frequency map tracking count of each character in window
    char_frequency: dict[str, int] = {}

    left = 0
    max_length = 0

    for right, char in enumerate(s):
        # EXPAND: Add character to window
        char_frequency[char] = char_frequency.get(char, 0) + 1

        # CONTRACT: Shrink window while we have more than K distinct characters
        # Unlike base template, we cannot jump — we must shrink incrementally
        # because removing one character might not restore the invariant
        while len(char_frequency) > k:
            left_char = s[left]
            char_frequency[left_char] -= 1

            # Remove character from map when its count reaches zero
            # This is crucial for correct distinct count via len(char_frequency)
            if char_frequency[left_char] == 0:
                del char_frequency[left_char]

            left += 1

        # UPDATE ANSWER: Window [left, right] has at most K distinct characters
        max_length = max(max_length, right - left + 1)

    return max_length

def length_of_longest_substring_two_distinct(s: str) -> int:
    """
    Find the length of the longest substring with at most 2 distinct characters.

    This is a direct application of the K-distinct template with K=2.
    """
    return length_of_longest_substring_k_distinct(s, k=2)

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

    Algorithm:
    - Build a frequency map of required characters from t
    - Expand window to include required characters
    - Once all requirements are satisfied, contract to find minimum
    - Track the best (smallest) valid window found

    Time Complexity: O(|s| + |t|) - linear in both string lengths
    Space Complexity: O(|t|) - frequency maps bounded by t's unique characters

    Args:
        s: Source string to search in
        t: Target string containing required characters

    Returns:
        Minimum window substring, or "" if no valid window exists
    """
    if not t or not s:
        return ""

    # State: Required character frequencies (what we need)
    need_frequency: dict[str, int] = {}
    for char in t:
        need_frequency[char] = need_frequency.get(char, 0) + 1

    # State: Current window character frequencies (what we have)
    have_frequency: dict[str, int] = {}

    # Tracking: How many unique characters have met their required frequency
    chars_satisfied = 0
    chars_required = len(need_frequency)

    # Answer tracking
    min_length = float('inf')
    min_window_start = 0

    left = 0

    for right, char in enumerate(s):
        # EXPAND: Add character to window
        have_frequency[char] = have_frequency.get(char, 0) + 1

        # Check if this character just satisfied its requirement
        # Important: Only count when we EXACTLY meet the requirement
        # (not when we exceed it, to avoid double counting)
        if char in need_frequency and have_frequency[char] == need_frequency[char]:
            chars_satisfied += 1

        # CONTRACT: Once all requirements satisfied, try to minimize window
        while chars_satisfied == chars_required:
            # UPDATE ANSWER: Current window is valid, check if it's the smallest
            window_length = right - left + 1
            if window_length < min_length:
                min_length = window_length
                min_window_start = left

            # Remove leftmost character and update state
            left_char = s[left]
            have_frequency[left_char] -= 1

            # Check if removing this character breaks the requirement
            # Important: Only decrement when we DROP BELOW the requirement
            if left_char in need_frequency and have_frequency[left_char] < need_frequency[left_char]:
                chars_satisfied -= 1

            left += 1

    # Return result
    if min_length == float('inf'):
        return ""
    return s[min_window_start : min_window_start + min_length]

def check_inclusion(s1: str, s2: str) -> bool:
    """
    Check if s2 contains any permutation of s1.

    A permutation means same characters with same frequencies.
    We use a fixed-size sliding window of length len(s1).

    Algorithm:
    - Build frequency map of s1 (the pattern)
    - Slide a window of size len(s1) over s2
    - Check if window frequency matches pattern frequency

    Time Complexity: O(|s1| + |s2|) - build pattern + single pass over s2
    Space Complexity: O(1) - at most 26 lowercase letters

    Args:
        s1: Pattern string (looking for its permutation)
        s2: Source string to search in

    Returns:
        True if s2 contains a permutation of s1
    """
    if len(s1) > len(s2):
        return False

    pattern_length = len(s1)

    # State: Frequency maps
    pattern_frequency: dict[str, int] = {}
    window_frequency: dict[str, int] = {}

    # Build pattern frequency map
    for char in s1:
        pattern_frequency[char] = pattern_frequency.get(char, 0) + 1

    # Optimization: Track how many characters have matching frequencies
    chars_matched = 0
    chars_to_match = len(pattern_frequency)

    for right, char in enumerate(s2):
        # EXPAND: Add character to window
        window_frequency[char] = window_frequency.get(char, 0) + 1

        # Update match count for added character
        if char in pattern_frequency:
            if window_frequency[char] == pattern_frequency[char]:
                chars_matched += 1
            elif window_frequency[char] == pattern_frequency[char] + 1:
                # We just exceeded the required count
                chars_matched -= 1

        # CONTRACT: Remove leftmost character when window exceeds pattern length
        if right >= pattern_length:
            left_char = s2[right - pattern_length]

            # Update match count for removed character
            if left_char in pattern_frequency:
                if window_frequency[left_char] == pattern_frequency[left_char]:
                    chars_matched -= 1
                elif window_frequency[left_char] == pattern_frequency[left_char] + 1:
                    # Removing brings us back to exact match
                    chars_matched += 1

            window_frequency[left_char] -= 1
            if window_frequency[left_char] == 0:
                del window_frequency[left_char]

        # CHECK: If all characters match, we found a permutation
        if chars_matched == chars_to_match:
            return True

    return False

def find_anagrams(s: str, p: str) -> list[int]:
    """
    Find all start indices of p's anagrams in s.

    This is an extension of the permutation check:
    instead of returning True on first match, collect all match positions.

    Time Complexity: O(|s| + |p|)
    Space Complexity: O(1) - bounded by alphabet size

    Args:
        s: Source string to search in
        p: Pattern string (looking for its anagrams)

    Returns:
        List of starting indices where anagrams of p begin in s
    """
    result: list[int] = []

    if len(p) > len(s):
        return result

    pattern_length = len(p)

    # State: Frequency maps
    pattern_frequency: dict[str, int] = {}
    window_frequency: dict[str, int] = {}

    for char in p:
        pattern_frequency[char] = pattern_frequency.get(char, 0) + 1

    chars_matched = 0
    chars_to_match = len(pattern_frequency)

    for right, char in enumerate(s):
        # EXPAND: Add character to window
        window_frequency[char] = window_frequency.get(char, 0) + 1

        if char in pattern_frequency:
            if window_frequency[char] == pattern_frequency[char]:
                chars_matched += 1
            elif window_frequency[char] == pattern_frequency[char] + 1:
                chars_matched -= 1

        # CONTRACT: Remove leftmost when window is full
        left = right - pattern_length + 1
        if left > 0:
            left_char = s[left - 1]

            if left_char in pattern_frequency:
                if window_frequency[left_char] == pattern_frequency[left_char]:
                    chars_matched -= 1
                elif window_frequency[left_char] == pattern_frequency[left_char] + 1:
                    chars_matched += 1

            window_frequency[left_char] -= 1
            if window_frequency[left_char] == 0:
                del window_frequency[left_char]

        # COLLECT: Record starting index if window is an anagram
        if chars_matched == chars_to_match:
            result.append(left)

    return result

def min_subarray_len(target: int, nums: list[int]) -> int:
    """
    Find the minimal length of a subarray whose sum is >= target.

    Algorithm:
    - Maintain a running sum of the current window
    - Expand window by adding elements
    - Once sum >= target, contract to find minimum length
    - Continue until all elements are processed

    Time Complexity: O(n) - each element added and removed at most once
    Space Complexity: O(1) - only tracking sum and pointers

    Args:
        target: Target sum to reach or exceed
        nums: Array of positive integers

    Returns:
        Minimum length of valid subarray, or 0 if none exists
    """
    n = len(nums)
    if n == 0:
        return 0

    # State: Running sum of current window
    window_sum = 0

    left = 0
    min_length = float('inf')

    for right, num in enumerate(nums):
        # EXPAND: Add element to window sum
        window_sum += num

        # CONTRACT: While sum satisfies target, try to minimize window
        # Note: We use 'while' not 'if' because multiple contractions may be possible
        while window_sum >= target:
            # UPDATE ANSWER: Current window is valid
            min_length = min(min_length, right - left + 1)

            # Remove leftmost element
            window_sum -= nums[left]
            left += 1

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

def maximize_window(sequence):
    state = {}
    left = 0
    max_result = 0

    for right, elem in enumerate(sequence):
        # Expand
        add_to_state(state, elem)

        # Contract while invalid
        while not is_valid(state):
            remove_from_state(state, sequence[left])
            left += 1

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

    return max_result

def minimize_window(sequence):
    state = {}
    left = 0
    min_result = float('inf')

    for right, elem in enumerate(sequence):
        # Expand
        add_to_state(state, elem)

        # Contract while valid (to minimize)
        while is_valid(state):
            min_result = min(min_result, right - left + 1)
            remove_from_state(state, sequence[left])
            left += 1

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

def fixed_window(sequence, k):
    state = {}
    result = []

    for right, elem in enumerate(sequence):
        # Expand
        add_to_state(state, elem)

        # Contract when window exceeds k
        if right >= k:
            remove_from_state(state, sequence[right - k])

        # Check condition when window is exactly k
        if right >= k - 1 and is_valid(state):
            result.append(process(state))

    return result