Dynamic Sliding Windows for Subarray/Substring Problems

1. The Sliding Window: A Dynamic Viewpoint

Imagine you have a pair of pointers, left and right, that define a "window" over a sequence (like an array or string). Unlike the fixed-size window problems you might have seen, here the window's size will dynamically grow and shrink.

• Expansion: The window grows by moving the right pointer to the right, including a new element.
• Contraction: The window shrinks by moving the left pointer to the right, excluding an element.

The core idea is to expand the window until it violates a given condition, and then contract it until it becomes valid again, all while keeping track of the best solution found so far.

This animation perfectly illustrates a variable-size window in action, finding the longest substring with unique characters.

This approach is highly efficient because it avoids re-calculating information for every possible subarray. Instead of a brute-force O(n²) solution, we process each element at most twice (once by the right pointer and once by the left), leading to an optimal O(n) time complexity.

2. The General Template for Variable-Size Windows

For a developer like yourself, thinking in terms of reusable templates is key. The variable-size sliding window pattern has a very consistent structure.

The template for finding a maximum length subarray/substring looks like this:

function findMaximumWindow(arr, condition) {
    let left = 0;
    let maxLength = 0;
    let windowState = {}; // Can be a hash map, a sum, etc.

    // 1. Expand the window with the 'right' pointer
    for (let right = 0; right < arr.length; right++) {
        // Update the state with the new element
        updateWindowState(windowState, arr[right], 'add');

        // 2. Shrink the window while the condition is violated
        while (/* condition is violated */) {
            // Update the state by removing the 'left' element
            updateWindowState(windowState, arr[left], 'remove');
            left++;
        }

        // 3. At this point, the window is valid.
        // Update the result.
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

This simple structure is incredibly powerful. Let's see it in action.

3. Application 1: Finding the Longest Substring

A classic application is finding the "Longest Substring with At Most K Distinct Characters". This pattern also covers variations like "Longest Substring Without Repeating Characters" (where K=1) and "Fruits into Baskets" (where K=2).

To understand the mechanics, let's watch a video that walks through these specific problems.

Let's recap the logic for "Longest Substring with At Most K Distinct Characters":

• windowState: A hash map (charFrequency) to store the counts of characters currently in the window.
• Condition Violation: The number of unique keys in our map is greater than K (Object.keys(charFrequency).length > K).
• Expansion (right pointer moves): Add the character str[right] to the map and/or increment its count.
• Contraction (left pointer moves):
  • Get the character str[left].
  • Decrement its count in the map.
  • If its count becomes 0, remove the character from the map.
  • Increment left.
• Update Result: After each valid expansion, maxLength = Math.max(maxLength, right - left + 1).

This GitHub resource provides a clean JavaScript implementation of this logic.

4. Application 2: Finding the Minimum Window

The pattern can also be adapted to find the shortest or minimum window that satisfies a condition. The template logic is slightly inverted.

Here, we expand until the condition is met, then shrink as much as possible while it remains met, updating our minimum length inside the shrinking loop.

The canonical problem for this is "Minimum Window Substring" (LeetCode 76), a notoriously difficult but common FAANG interview question. Acing this demonstrates a deep understanding of the sliding window pattern.

The logic for finding a minimum length window is:

1. Expand the window by moving right until the condition is satisfied (e.g., have === need).
2. Once satisfied, enter a while loop that shrinks the window from the left:
   • Update the minLength with the current window size.
   • Move left one step to the right.
   • Update the windowState.
   • The loop continues as long as the condition remains satisfied.
3. When the condition is broken by shrinking, exit the inner loop and go back to step 1 (expanding).

5. How to Recognize the Pattern

You're aiming to spot these patterns quickly in an interview. Here are some strong clues that a variable-size sliding window might be the answer.

In summary, look for problems involving:

• Contiguous arrays or substrings.
• Finding the longest, shortest, maximum, or minimum subarray/substring.
• Constraints like "at most K", "at least K", "contains all characters", or "sum >= target".

Conclusion

You've now learned the variable-size sliding window, a fundamental pattern for solving a huge class of array and string problems efficiently. By recognizing the problem type and applying the correct template (find maximum vs. find minimum), you can consistently turn a brute-force O(n²) problem into an optimal O(n) solution.

Key Takeaways:

• The variable-size sliding window uses left and right pointers to define a dynamic window over a sequence.
• The core mechanic is to expand the window with right and contract it with left based on whether a condition is met or violated.
• For "longest/maximum" problems, you shrink when the condition is violated and update the result after every valid expansion.
• For "shortest/minimum" problems, you expand until the condition is met, then shrink as much as possible while it remains met, updating your result inside the shrinking loop.
• This pattern provides an optimal O(n) time and often O(k) or O(1) space solution.

Preview of the Next Lesson:
We will continue with the sliding window pattern, but focus on a specific, powerful variation: using a fixed-size window combined with a frequency map. This is perfect for problems like "Find All Anagrams in a String" and is a direct and logical next step in your journey to mastering these techniques. See you then