Sliding Window
The sliding window pattern maintains a window (subarray or substring) that expands or contracts to find optimal subarrays satisfying certain constraints. Instead of recalculating from scratch for each possible subarray, the window incrementally adds and removes elements, achieving O(n) time. This pattern is essential for substring and subarray optimization problems.
When to Use
- →You need to find a subarray or substring with a specific property (longest, shortest, containing certain characters)
- →The problem involves contiguous elements in an array or string
- →You need to track a running sum, count, or frequency within a range
- →A brute-force approach would check all O(n^2) subarrays
Approach
The sliding window uses two pointers (left and right) that define the current window. The right pointer expands the window by including new elements, and the left pointer contracts it when constraints are violated. You maintain a running state (sum, frequency map, count) that updates incrementally.
For fixed-size windows, advance both pointers together. For variable-size windows, expand right until the window becomes invalid, then shrink from the left until it's valid again. Track the best answer found during this process.
The hardest part is determining when to shrink. For "minimum window substring" problems, shrink whenever the window satisfies the constraint (to find the minimum). For "longest substring without repeating" problems, shrink whenever a constraint is violated (to maintain validity).
Code Template
// Variable-size sliding window (find longest valid window)
function longestValidWindow(s) {
const freq = new Map();
let left = 0, maxLen = 0;
for (let right = 0; right < s.length; right++) {
freq.set(s[right], (freq.get(s[right]) || 0) + 1);
// Shrink while window is invalid
while (/* window is invalid */) {
freq.set(s[left], freq.get(s[left]) - 1);
if (freq.get(s[left]) === 0) freq.delete(s[left]);
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// Minimum window containing all target characters
function minWindow(s, t) {
const need = new Map();
for (const c of t) need.set(c, (need.get(c) || 0) + 1);
let have = 0, required = need.size;
let left = 0, minLen = Infinity, minStart = 0;
const window = new Map();
for (let right = 0; right < s.length; right++) {
const c = s[right];
window.set(c, (window.get(c) || 0) + 1);
if (need.has(c) && window.get(c) === need.get(c)) have++;
while (have === required) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
const d = s[left];
window.set(d, window.get(d) - 1);
if (need.has(d) && window.get(d) < need.get(d)) have--;
left++;
}
}
return minLen === Infinity ? "" : s.slice(minStart, minStart + minLen);
}