Sliding Window: Summary ​

The Sliding Window technique is a powerful method for solving problems involving contiguous subarrays or substrings. It optimizes brute-force approaches by maintaining a dynamic "window" over a portion of the data, defined by left and right pointers. This avoids redundant calculations, typically reducing the time complexity from (O(n^2)) to a much more efficient (O(n)).

What It Is & When To Use It ​

Use the Sliding Window pattern when the problem asks for an optimal value within a contiguous subarray/substring.

Core Idea: Create a window over the data. Expand the window by moving the right pointer. When a certain condition is met or violated, contract the window by moving the left pointer.

Signals for Sliding Window:

• Input Data: The problem involves an Array, String, or List.
• Keywords: "longest substring", "minimum window", "smallest subarray", "contiguous subarray of size k".
• Goal: You need to find a subarray or substring that satisfies a certain property.

I. The Core Distinction: Fixed vs. Variable Size ​

Identifying the window type is the most critical first step.

1. Fixed-Size Window ​

The problem specifies a fixed window size, k. This is the simpler pattern.

• When to Use: The problem explicitly says "subarray of size k" or "substring of length k".
• Logic: Once the window reaches size k, you slide it forward one step at a time. In each step, you add the new right element and remove the left element, keeping the size constant.

Core Template (Fixed-Size):

def fixed_window(arr, k):
    left = 0
    # ... initialize window_state, answer ...

    for right in range(len(arr)):
        # EXPAND window by adding arr[right] to state
        
        # Once window is full, PROCESS and SHRINK
        if (right - left + 1) == k:
            # ... update answer (e.g., max_sum = max(max_sum, current_sum)) ...
            # ... remove arr[left] from state ...
            left += 1
            
    return # your answer

2. Variable-Size Window ​

The problem asks you to find the longest or shortest window that satisfies a property. The size is not given.

• When to Use: Keywords are "longest", "shortest", "minimum", "maximum" subarray/substring that meets a condition (e.g., sum >= target, <= k distinct characters).
• Logic: Expand the window by moving right. Use a while loop to shrink the window from the left only when a condition is violated (for "longest" windows) or as long as a condition is met (for "shortest" windows).

Core Template (Variable-Size):

def variable_window(arr, condition):
    left = 0
    # ... initialize window_state, answer ...

    for right in range(len(arr)):
        # EXPAND window by adding arr[right] to state
        
        # CONTRACT window based on the condition
        while not is_window_valid(window_state):
            # ... remove arr[left] from state ...
            left += 1
        
        # UPDATE answer with the current valid window size
        # ans = max(ans, right - left + 1) for longest
        # ans = min(ans, right - left + 1) for shortest (inside the while loop)
            
    return # your answer

II. Key Sub-Patterns & Decision Points ​

1. Longest vs. Shortest Window ​

This determines where you update your answer.

• Longest Window: You have a potential answer at every valid step. Update the max_len after the shrinking while loop, as the window is guaranteed to be valid at that point.
• Shortest Window: You only have a potential answer once the condition is met. Update the min_len inside the shrinking while loop, right before you try to make the window even shorter.

2. State Management ​

The data structure you use to track the window's state is crucial.

• Sum: Use a single integer variable (current_sum). Watch out for negative numbers, which can break simple shrinking logic.
• Frequency: Use a hash map (defaultdict or Counter) for character/number frequencies. For a small, fixed character set (e.g., 'a'-'z'), a simple array of size 26 is a common and efficient optimization.
• Uniqueness: Use a set to track unique elements in the window.

3. "Exactly K" vs. "At Most K" ​

A common and tricky variation involves counting subarrays with a specific number of distinct elements.

• "At Most K": This is a standard variable-size window problem where the shrink condition is len(hash_map) > k.
• "Exactly K": This cannot be solved directly with one sliding window. The key is to use the principle of inclusion-exclusion:
  • count(exactly K) = count(at_most K) - count(at_most K - 1)
  • This transforms one hard problem into two solvable ones. The at_most helper function uses a specific counting formula: count += right - left + 1 at each valid step.