Sliding window pattern

Grow the right edge, shrink the left edge while invalid.

Part 1 of 5

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.

Why it works

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.

Contiguous subarray or substringLongest or shortest window with a propertyAt most K distinct, no repeats, sum at least S
Part 2 of 5

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.

Problem

Find the smallest substring of s that contains every character of t (with multiplicity).

Plan before you code

  1. Count what t needs.
  2. Expand right; when a need is met, decrement 'missing'.
  3. While nothing is missing, record the window and shrink from the left.
Part 3 of 5

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

TypeScriptKotlinJava
longest-window-that.tsTypeScriptCopy
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}
14 linesUTF-8TypeScript
longest-window-that.ktKotlinCopy
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}
15 linesUTF-8Kotlin
longest-window-that.javaJavaCopy
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}
14 linesUTF-8Java
  1. Extend the right edge and record the new character.
  2. Shrink from the left until the window is valid again.
  3. Every valid window is a candidate answer.

3.2Solution

Strict TypeScript, type-checked and tested.

Minimum Window Substring

TypeScriptKotlinJava
minimum-window-substring.tsTypeScriptCopy
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}
21 linesUTF-8TypeScript
minimum-window-substring.ktKotlinCopy
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}
23 linesUTF-8Kotlin
minimum-window-substring.javaJavaCopy
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}
21 linesUTF-8Java

Step by step

  1. need counts what t requires; missing is how many are still owed.
  2. Grow right and pay off a need when you can.
  3. Window covers t: keep it if it is the smallest so far.
  4. Shrink left; giving back a needed character breaks the window.

Complexity: O(|s| + |t|) time, O(alphabet) space

Part 4 of 5

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?
When shrinking the window does not reliably move it towards valid, for example sums with negative numbers. Use prefix sums with a hash map there.
Fixed or variable window?
Fixed size k: move both ends together. Variable: grow right, and shrink left while the window breaks the rule (for the longest) or while it still satisfies it (for the shortest).
How do you know every required character is covered in O(1)?
Keep a count of how many required characters are still missing, and update it only when a character's count crosses zero.

4.2Solo practice

Try these without looking; open the hint only when stuck.

EasyMaximum Sum Subarray of Size K
Hint

Fixed-size window: add right, subtract the element leaving.

Part 5 of 5

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
Medium

Longest Repeating Character Replacement

Replace at most k characters to get the longest run of one letter.

  1. A window is valid if length − (count of its most common letter) ≤ k.
  2. Grow right; shrink left while invalid.
  3. The max count never needs to decrease for the answer to stay correct.
longest-repeating-character.tsTypeScriptCopy
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}
15 linesUTF-8TypeScript

Complexity: O(n) time, O(1) space (26 letters)

Hard

Sliding Window Maximum

Return the maximum of every window of size k.

  1. Keep a deque of indices whose values are decreasing.
  2. A new value evicts smaller ones: they can never be a maximum again.
  3. The front is the maximum; drop it when it leaves the window.
sliding-window-maximum.tsTypeScriptCopy
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}
12 linesUTF-8TypeScript

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)