Basics
The idea behind the pattern, why it is correct, and the clues in a question that point to it.
1.1Core idea
What the pattern does, in plain words.
Keep a window [left, right]. Extend right one step at a time and update counts. While the window breaks the rule, move left forward. Every index enters and leaves once.
A window from left to right holds the current candidate. Moving right adds one element and moving left removes one, so counts are updated in O(1) instead of recomputing every subarray. Each index enters and leaves the window at most once, which gives O(n).
Typical cost: O(n) time, O(k) space for the window state
1.2Recognition signals
If a question has one of these clues, try this pattern first.
Question
A classic interview problem from this family. Read it carefully and plan the approach before writing any code.
2.1Minimum Window Substring
The problem statement, then the plan you would say out loud.
Find the smallest substring of s that contains every character of t (with multiplicity).
Plan before you code
- Count what t needs.
- Expand right; when a need is met, decrement 'missing'.
- While nothing is missing, record the window and shrink from the left.
Detailed answer
First the reusable template, then the worked solution built from it and a walk through it one step at a time.
3.1Template
Memorise this shape. Most problems in this family are this code plus one twist.
Longest window that satisfies a rule
1function longestWindow(s: string): number {2 const count = new Map<string, number>();3 let left = 0, best = 0;4 for (let right = 0; right < s.length; right++) {5 const ch = s[right];6 count.set(ch, (count.get(ch) ?? 0) + 1);7 while (count.get(ch)! > 1) { // window invalid8 count.set(s[left], count.get(s[left])! - 1);9 left++;10 }11 best = Math.max(best, right - left + 1);12 }13 return best;14}1fun longestWindow(s: String): Int {2 val count = HashMap<Char, Int>()3 var left = 04 var best = 05 for (right in s.indices) {6 val ch = s[right]7 count[ch] = (count[ch] ?: 0) + 18 while (count.getValue(ch) > 1) { // window invalid9 count[s[left]] = count.getValue(s[left]) - 110 left++11 }12 best = maxOf(best, right - left + 1)13 }14 return best15}1static int longestWindow(String s) {2 Map<Character, Integer> count = new HashMap<>();3 int left = 0, best = 0;4 for (int right = 0; right < s.length(); right++) {5 char ch = s.charAt(right);6 count.merge(ch, 1, Integer::sum);7 while (count.get(ch) > 1) { // window invalid8 count.merge(s.charAt(left), -1, Integer::sum);9 left++;10 }11 best = Math.max(best, right - left + 1);12 }13 return best;14}- Extend the right edge and record the new character.
- Shrink from the left until the window is valid again.
- Every valid window is a candidate answer.
3.2Solution
Strict TypeScript, type-checked and tested.
Minimum Window Substring
1function minWindow(s: string, t: string): string {2 const need = new Map<string, number>();3 for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);4 let missing = t.length;5 let left = 0, bestLo = 0, bestLen = Infinity;6 for (let right = 0; right < s.length; right++) {7 const ch = s[right];8 if ((need.get(ch) ?? 0) > 0) missing--;9 need.set(ch, (need.get(ch) ?? 0) - 1);10 while (missing === 0) {11 if (right - left + 1 < bestLen) {12 bestLo = left;13 bestLen = right - left + 1;14 }15 const out = s[left++];16 need.set(out, need.get(out)! + 1);17 if (need.get(out)! > 0) missing++;18 }19 }20 return bestLen === Infinity ? "" : s.slice(bestLo, bestLo + bestLen);21}1fun minWindow(s: String, t: String): String {2 val need = HashMap<Char, Int>()3 for (ch in t) need[ch] = (need[ch] ?: 0) + 14 var missing = t.length5 var left = 06 var bestLo = 07 var bestLen = Int.MAX_VALUE8 for (right in s.indices) {9 val ch = s[right]10 if ((need[ch] ?: 0) > 0) missing--11 need[ch] = (need[ch] ?: 0) - 112 while (missing == 0) {13 if (right - left + 1 < bestLen) {14 bestLo = left15 bestLen = right - left + 116 }17 val out = s[left++]18 need[out] = need.getValue(out) + 119 if (need.getValue(out) > 0) missing++20 }21 }22 return if (bestLen == Int.MAX_VALUE) "" else s.substring(bestLo, bestLo + bestLen)23}1static String minWindow(String s, String t) {2 Map<Character, Integer> need = new HashMap<>();3 for (char ch : t.toCharArray()) need.merge(ch, 1, Integer::sum);4 int missing = t.length();5 int left = 0, bestLo = 0, bestLen = Integer.MAX_VALUE;6 for (int right = 0; right < s.length(); right++) {7 char ch = s.charAt(right);8 if (need.getOrDefault(ch, 0) > 0) missing--;9 need.merge(ch, -1, Integer::sum);10 while (missing == 0) {11 if (right - left + 1 < bestLen) {12 bestLo = left;13 bestLen = right - left + 1;14 }15 char out = s.charAt(left++);16 need.merge(out, 1, Integer::sum);17 if (need.get(out) > 0) missing++;18 }19 }20 return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestLo, bestLo + bestLen);21}Step by step
- need counts what t requires; missing is how many are still owed.
- Grow right and pay off a need when you can.
- Window covers t: keep it if it is the smallest so far.
- Shrink left; giving back a needed character breaks the window.
Complexity: O(|s| + |t|) time, O(alphabet) space
Q&A
What interviewers ask once your code works, and problems to try on your own.
4.1Interview questions
Answer out loud, then open.
When does a sliding window fail?
Fixed or variable window?
How do you know every required character is covered in O(1)?
4.2Solo practice
Try these without looking; open the hint only when stuck.
Hint
Fixed-size window: add right, subtract the element leaving.
Extra depth
More fully worked problems in the same family, and the mistakes that cost offers.
5.12 more worked problems
Each one: the problem, the plan, the code and its cost.
Show detailsHide details
Longest Repeating Character Replacement
Replace at most k characters to get the longest run of one letter.
- A window is valid if length − (count of its most common letter) ≤ k.
- Grow right; shrink left while invalid.
- The max count never needs to decrease for the answer to stay correct.
1function characterReplacement(s: string, k: number): number {2 const count = new Map<string, number>();3 let left = 0, top = 0, best = 0;4 for (let right = 0; right < s.length; right++) {5 const c = (count.get(s[right]) ?? 0) + 1;6 count.set(s[right], c);7 top = Math.max(top, c);8 while (right - left + 1 - top > k) {9 count.set(s[left], count.get(s[left])! - 1);10 left++;11 }12 best = Math.max(best, right - left + 1);13 }14 return best;15}Complexity: O(n) time, O(1) space (26 letters)
Sliding Window Maximum
Return the maximum of every window of size k.
- Keep a deque of indices whose values are decreasing.
- A new value evicts smaller ones: they can never be a maximum again.
- The front is the maximum; drop it when it leaves the window.
1function maxSlidingWindow(nums: number[], k: number): number[] {2 const dq: number[] = []; // indices; values decrease from head to back3 let head = 0;4 const out: number[] = [];5 for (let i = 0; i < nums.length; i++) {6 while (dq.length > head && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();7 dq.push(i);8 if (dq[head] <= i - k) head++;9 if (i >= k - 1) out.push(nums[dq[head]]);10 }11 return out;12}Complexity: O(n) time, O(k) space
5.2Traps
Bugs and misreadings that come up again and again with this pattern.
Show detailsHide details
- Using a window on non-contiguous problems
- Shrinking with if instead of while
- Off-by-one in window length (right - left + 1)