The Sliding Window Pattern: Taming Contiguous Subarrays
Whenever a problem asks for the 'longest', 'shortest', or 'maximum' of a contiguous subarray or substring, a brute-force nested loop is usually the first thing that comes to mind. The Sliding Window pattern is the elegant, linear-time alternative.
Introduction
If you are dealing with arrays or strings and the problem statement includes the word "contiguous" (meaning elements right next to each other), you are almost certainly looking at a Sliding Window problem.
The brute force approach to finding a specific contiguous sub-section is to use a nested loop: checking every possible start point, and then iterating through every possible end point. This results in a massive $O(N^2)$ time complexity.
The Sliding Window technique allows us to achieve the exact same result in just a single pass—dropping the time complexity to $O(N)$.
The Core Concept
Imagine a physical window frame sliding over an array of numbers.
The window has a left boundary and a right boundary.
- We expand the window by moving the
rightboundary forward. - If our window becomes invalid (e.g., it gets too large, or it contains duplicate characters), we shrink it by dragging the
leftboundary forward until the window is valid again.
This dynamic accordion-like movement ensures we only process each element a maximum of two times (once when it enters the window, and once when it leaves).
Example: Longest Substring Without Repeating Characters
Let's look at LeetCode #3. We need to find the length of the longest substring without repeating characters in the string "abcabcbb".
Step-by-Step Execution:
- Initialize:
left = 0,right = 0. Our window is empty. - Expand:
rightpoints to'a'. Not in our set. Add it. Window:[a]. Max Length = 1. - Expand:
rightmoves to'b'. Add it. Window:[a, b]. Max Length = 2. - Expand:
rightmoves to'c'. Add it. Window:[a, b, c]. Max Length = 3. - Conflict!
rightmoves to the second'a'. It's already in our set! - Shrink: We must move our
leftpointer forward and remove characters from our set until the duplicate'a'is gone. We remove the first'a', moveleftto index 1, and add the new'a'. Window is now[b, c, a].
By constantly pushing right forward and only pulling left forward when we break a rule, we scan the entire string efficiently without ever going backwards.
Why this is brilliant
- Time Complexity: $O(N)$ — In the worst-case scenario, each character is visited exactly twice (once by the
rightpointer, once by theleftpointer). - Space Complexity: $O(K)$ — Where K is the size of the HashSet (bounded by the character alphabet).
Master the accordion motion of the left and right pointers, and substring problems will never intimidate you again.
Implementation
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> window = new HashSet<>();
int left = 0, maxLength = 0;
for (int right = 0; right < s.length(); right++) {
// If we find a duplicate, shrink the window from the left
while (window.contains(s.charAt(right))) {
window.remove(s.charAt(left));
left++;
}
// Expand the window with the new character
window.add(s.charAt(right));
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}