When to use. Contiguous subarray/substring; constraint is monotonic as the window grows or shrinks.
Complexity. Time O(n) — each index enters and leaves at most once. Space O(k) for the alphabet or distinct keys in the window.
Who gets asked. Fixed windows show up in intern screens. Variable windows with a counter map are mid-level staples.
Prereq. Arrays & strings; hash tables for character counts.
Sliding Window
A contiguous range that grows and shrinks as you scan. The constraint must get worse (or stay) as the window grows — that is what makes the two pointers monotonic.
The idea
Fixed window: size k is given. Maintain a running sum or a deque of candidates. Slide by dropping index i−k and adding i. Time O(n).
Variable window: right always advances; left advances while the window is invalid (too many distinct chars, sum too large, more than k replacements). Because left only moves forward, total work is O(n).
If shrinking the window does not restore a simple invariant (non-monotonic constraint), this is not a window problem — try prefix sums or DP.
Worked example
Longest run with at most k distinct
A string and an integer k. Longest substring that uses at most k different characters. Example: "eceba", k = 2 → "ece" length 3.
Expand right, increment a count map.
While the map has more than k keys, decrement s[left] and bump left.
Track max of right−left+1. Each index enters and leaves the window once.
function longestAtMostK(s, k) {
const count = new Map();
let left = 0;
let best = 0;
for (let right = 0; right < s.length; right++) {
count.set(s[right], (count.get(s[right]) || 0) + 1);
while (count.size > k) {
const ch = s[left];
count.set(ch, count.get(ch) - 1);
if (count.get(ch) === 0) count.delete(ch);
left += 1;
}
best = Math.max(best, right - left + 1);
}
return best;
}
Time O(n). Space O(k) for the distinct keys in the window.
Practice shapes
Original prompts — same family as interview questions, not copied statements.
Fixed-size max sum
Numbers and window size k. Maximum sum of any contiguous k elements.
Aim: O(n) time, O(1) space
Smallest covering range
A source string and a set of required characters (with duplicates). Shortest substring that covers every required character at least as often as the set asks.
Aim: O(n) time over a small alphabet
At most k replacements
A string of uppercase letters and k. Longest substring you can make all-equal by changing at most k letters inside it.