Sliding Window Pattern

The Sliding Window pattern is a powerful algorithmic technique used to track and optimize properties of contiguous subarrays, substrings, or subsegments in linear structures (like arrays or strings). Instead of recomputing each subsegment from scratch in $O(N^2)$ or $O(N cdot K)$ time, the pattern maintains a running state (representing a "window") and updates it in $O(1)$ time by incrementally incorporating the new element entering the window from the right and discarding the old element leaving the window from the left.

By avoiding redundant work, Sliding Window transforms expensive brute-force searches into highly efficient $O(N)$ linear scans.

---

The Core Concept: Longest Substring Without Repeating Characters

To understand this concept deeply, let's explore Longest Substring Without Repeating Characters.

Problem Statement: Given a string s, find the length of the longest substring without repeating characters.

Naive Brute Force — $O(N^2)$

A naive solution checks all possible substrings and determines if each has unique characters:

This is highly inefficient because it repeatedly checks overlapping characters from scratch, resulting in a time complexity of $O(N^2)$ (or $O(N^3)$ depending on string slicing and character set checks).

The Sliding Window Breakthrough — $O(N)$

Instead of starting from scratch for each substring, we use a variable-length sliding window represented by two pointers: left and right. We also maintain a hash map (char_map) that stores the most recent index of each character we have processed.

As right expands the window by iterating through the string:

• If the current character is a duplicate that has already been seen inside our current window boundaries (char_map[char] >= left), we immediately shrink or jump the left pointer to char_map[char] + 1.
• We then record/update the current character's new index in char_map.
• We calculate the current window's size (right - left + 1) and update our running maximum length (max_len).

This decision rule allows the window to slide forward and discard invalid subsegments in $O(1)$ time.

---

Step-by-Step Traversal

Let's trace the algorithm on the string: "abcabcbb".

Step 1: Initialization

We initialize char_map to store characters' last seen indices, left = 0 to mark the start of the window, and max_len = 0 to track the maximum length of any unique substring.

Step 2: Processing First Three Characters ('a', 'b', 'c')

As right moves from index 0 to 2, the characters 'a', 'b', and 'c' are added to char_map.

• At right = 0 (character 'a'), the window is ["a"] (length 1), and max_len becomes 1.

• At right = 1 (character 'b'), the window is ["a", "b"] (length 2), and max_len becomes 2.

• At right = 2 (character 'c'), the window is ["a", "b", "c"] (length 3), and max_len becomes 3.

Step 3: Encountering First Duplicate ('a' at index 3)

At right = 3, we see 'a'. Since 'a' is already in our map at index 0 (which is $ge \text{left}$), we have a duplicate in our current window.

To resolve this, we contract the window by moving left to char_map['a'] + 1, which is index 1. The window is now ["b", "c", "a"].

We update the map to char_map['a'] = 3. The current window length is 3, so max_len remains 3.

Step 4: Encountering Second Duplicate ('b' at index 4)

At right = 4, we see 'b'. It is in the map at index 1 ($ge \text{left}$), so we have a duplicate.

We contract the window by moving left to char_map['b'] + 1, which is index 2. The window becomes ["c", "a", "b"].

We update char_map['b'] = 4. The current window length is 3, so max_len remains 3.

Step 5: Encountering Third Duplicate ('c' at index 5)

At right = 5, we see 'c'. It is in the map at index 2 ($ge \text{left}$), so we have a duplicate.

We contract the window by moving left to char_map['c'] + 1, which is index 3. The window becomes ["a", "b", "c"].

We update char_map['c'] = 5. The current window length is 3, so max_len remains 3.

Step 6: Encountering Fourth Duplicate ('b' at index 6)

At right = 6, we see 'b'. It is in the map at index 4 ($ge \text{left}$), so we have a duplicate.

We contract the window by moving left to char_map['b'] + 1, which is index 5. The window becomes ["c", "b"] (length 2).

We update char_map['b'] = 6. The current window length is 2, so max_len remains 3.

Step 7: Encountering Fifth Duplicate ('b' at index 7)

At right = 7, we see 'b'. It is in the map at index 6 ($ge \text{left}$), so we have a duplicate.

We contract the window by moving left to char_map['b'] + 1, which is index 7. The window becomes ["b"] (length 1).

We update char_map['b'] = 7. The current window length is 1, so max_len remains 3.

Step 8: Done

The loop terminates, and we return the final maximum length max_len = 3.

---

Code Implementation

Time Complexity: $O(N)$ — we scan the string with the right pointer once, and the left pointer only moves forward, visiting each element at most once. Space Complexity: $O(\min(N, M))$ — where $M$ is the size of the character set, as we store at most $M$ unique characters in the map.

---

Core Variations

1. Fixed-Size Sliding Window

The window size is constant. We expand the window to size $K$ initially, and then for each subsequent step, we add the new element on the right and remove the oldest element on the left to maintain the exact size $K$.

• Use when: searching for properties of subarrays of a fixed, predetermined length.
• Examples: Maximum Sum Subarray of Size K, Permutation in String.

2. Variable-Size Sliding Window (Dynamic Expansion)

The window grows and shrinks dynamically based on a constraint. We expand the right pointer to include new elements until the constraint is violated, and then we shrink the left pointer until the constraint is satisfied again.

• Use when: searching for the longest/shortest subarray satisfying a dynamic constraint.
• Examples: Longest Substring Without Repeating Characters, Minimum Size Subarray Sum.

3. Sliding Window with Auxiliary Tracker

In addition to pointers, we use a hash map, frequency array, or set to track counts, frequencies, or indices of elements currently inside the window.

• Use when: window validity depends on character counts or frequencies.
• Examples: Longest Repeating Character Replacement, Minimum Window Substring.

---

When Do I Use This?

Check if the problem satisfies these conditions:

1. The input is a linear structure like an array, string, or linked list.
2. The problem asks for a contiguous subarray, substring, or subsegment (e.g., "longest", "shortest", "maximum", "minimum").
3. Checking all possible contiguous subarrays takes $O(N^2)$ or $O(N^3)$ time, but window state updates can be done incrementally in $O(1)$ time.

If these apply, Sliding Window is the optimal pattern.

---

Practice Problems