Sliding Window Technique for Subarray/Substring Problems

1. The Sliding Window: A Conceptual Overview

At its core, the sliding window pattern is about maintaining a "window" (a contiguous sub-array or substring) and moving its endpoints through the larger data structure. Instead of re-computing the properties of every possible subarray from scratch, you update the window's state by adding an element at one end and, when necessary, removing an element from the other.

There are two main types of sliding window problems, and identifying which type you're dealing with is the first step to a solution.

2. Fixed-Length Sliding Window

This is the simpler of the two patterns. You use it when the problem specifies a fixed size, k, for the subarray or substring you're interested in.

The logic is straightforward:

1. Create an initial window of size k.
2. Calculate the desired metric (e.g., sum, average, character count) for this first window.
3. Slide the window one element at a time until you reach the end of the array.
4. In each slide, add the new element that enters the window and subtract the element that leaves the window. This O(1) update is far more efficient than re-calculating everything.
5. Update your global answer at each step.

The article "Fixed Length Sliding Window" from HelloInterview provides an excellent textual explanation and a clean template.

Fixed-Length Template

As you saw in the article, the structure for a fixed-length window is very consistent. Here is the general template you can adapt:

def fixed_length_sliding_window(arr, k):
    # Initialize pointers and state
    start = 0
    current_window_state = ... # e.g., a sum, a hash map
    result = ...

    for end in range(len(arr)):
        # Update state by adding the new element arr[end]
        update_state_add(arr[end])

        # Once the window reaches size k, start sliding
        if (end - start + 1) == k:
            # 1. Process the current window, update result
            update_result(current_window_state)

            # 2. Update state by removing the old element arr[start]
            update_state_remove(arr[start])

            # 3. Slide the window forward
            start += 1
    
    return result

3. Variable-Length Sliding Window

This pattern is more dynamic and powerful. You use it when the window size isn't fixed but must conform to some property (e.g., "contains no more than 2 distinct characters," or "has a sum less than a target").

The general logic involves two pointers, start and end, and a while loop nested inside a for loop:

1. The end pointer expands the window by moving to the right, one element at a time.
2. At each step, you add the new element to your window's state.
3. After adding the new element, you check if the window's state is still valid.
4. If the window is invalid, you enter a while loop that shrinks the window from the left by moving the start pointer to the right until the window becomes valid again.
5. After ensuring the window is valid, you can update your answer (e.g., record the maximum length found so far).

"Longest Substring Without Repeating Characters" is the quintessential variable-length sliding window problem. Let's see a detailed walkthrough.

Variable-Length Template

The key to this pattern is the while loop that contracts the window. The resource from HelloInterview provides a great template for this logic.

This gives us the following general structure:

def variable_length_sliding_window(arr):
    start = 0
    result = ...
    current_window_state = ...

    for end in range(len(arr)):
        # 1. Expand the window by including arr[end]
        update_state_add(arr[end])

        # 2. While the window is invalid, contract it from the left
        while not is_window_valid(current_window_state):
            update_state_remove(arr[start])
            start += 1
        
        # 3. Now the window is valid. Update the result.
        #    (e.g., max_length = max(max_length, end - start + 1))
        update_result(...)

    return result

4. How to Spot a Sliding Window Problem

Recognizing when to use this pattern is half the battle. Here are some strong cues to look for in a problem description:

• Input: The problem involves a linear data structure like an array, linked list, or string.
• Output: You are asked to find the longest/shortest/maximum/minimum value of a contiguous subarray or substring.
• Keywords: Look for phrases like "subarray," "substring," "contiguous," "min/max length," "at most k," etc.

For a rapid-fire summary of these cues and more examples, the following video is helpful.

Conclusion

You've now added another powerful, optimal pattern to your interview toolkit. The sliding window technique elegantly transforms brute-force problems into linear-time solutions, a trade-off that interviewers love to see.

Key Takeaways:

• Core Idea: The sliding window pattern processes arrays or strings by maintaining a "window" and sliding it across the data, updating a state incrementally rather than re-computing from scratch. This reduces time complexity from O(n²) to O(n).
• Fixed-Length Window: Use when the problem specifies a subarray/substring of a fixed size k. The logic involves adding the end element and removing the start element in each step.
• Variable-Length Window: Use when the window must satisfy a certain property and its size is not given. The logic involves expanding with an end pointer and contracting with a start pointer whenever the property is violated.
• Problem Recognition: Look for problems involving contiguous subarrays/substrings on linear data structures, especially those asking for a min/max value under certain constraints.

In our next lesson, we will explore another technique for efficiently handling array problems: prefix sums. This method is perfect for answering range query problems in O(1) time after an initial O(n) preprocessing step.