Engineering Notes
Home/Algorithms & Coding Interviews/Arrays, Strings & Linear Structures/Sliding Window
Algorithms & Coding Interviews · Arrays, Strings & Linear Structures

Sliding Window

Sliding windows turn 'check every subarray' into one O(n) pass. Learn the longest-valid and shortest-valid templates, what state to keep in the window, why the nested loop is still linear, and watch six LeetCode problems, up to Minimum Window Substring, animated step by step.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 11 min read▶ 3 interactive🛠️ 4 exercises

🎯 What you'll learn

  • Recognizing contiguous-range problems
  • Longest-valid vs shortest-valid vs fixed windows
  • Window state: sums, counts, last-index maps, 'formed' counters
  • Six LeetCode problems with animated walkthroughs

📚 Before you start

Part 1The Pattern

A sliding window keeps a contiguous range [left, right] and updates its state incrementally instead of recomputing it for every subarray. The right edge expands one step at a time; the left edge moves forward only when the window becomes invalid. Since both edges only move forward, the whole scan is O(n), compared with O(n²) or O(n³) for checking every subarray.

A window over a string expanding on the right and shrinking on the left
A window over a string expanding on the right and shrinking on the left

1Recognition Cues

  • "longest / shortest / maximum / minimum contiguous subarray or substring such that…"
  • "at most k distinct", "without repeating characters", "with sum ≥ target", "containing all characters of t"
  • "every window of size k" (fixed window)

The key requirement: validity must be monotonic. If a window is invalid, every larger window containing it is also invalid (for "longest" problems), so shrinking is always the right move. With negative numbers and an exact-sum condition this breaks; use prefix sums + hash map instead (04-prefix_sums).

2Templates

Variable window for "longest valid" problems, and a fixed-size window:

typescript
function longestAtMostKDistinct(s: string, k: number): number {
  const counts = new Map<string, number>();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    counts.set(s[right], (counts.get(s[right]) ?? 0) + 1);
    while (counts.size > k) {
      const d = s[left++];
      counts.set(d, counts.get(d)! - 1);
      if (counts.get(d) === 0) counts.delete(d);
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

function maxSumFixed(nums: number[], k: number): number {
  let window = nums.slice(0, k).reduce((a, b) => a + b, 0), best = window;
  for (let i = k; i < nums.length; i++) {
    window += nums[i] - nums[i - k];
    best = Math.max(best, window);
  }
  return best;
}
python
def longest_at_most_k_distinct(s, k):
    counts = {}
    left = best = 0
    for right, c in enumerate(s):
        counts[c] = counts.get(c, 0) + 1          # 1. expand: add s[right]
        while len(counts) > k:                    # 2. shrink while invalid
            d = s[left]
            counts[d] -= 1
            if counts[d] == 0:
                del counts[d]
            left += 1
        best = max(best, right - left + 1)        # 3. window [left, right] is valid
    return best

def max_sum_fixed(nums, k):                       # fixed-size window
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]           # add the new, drop the old
        best = max(best, window)
    return best

For "shortest valid" problems (minimum window, minimum size subarray), the loop flips: expand until the window is valid, then shrink while it stays valid, recording the answer inside the shrinking loop.

text
longest:   for right: add(right); while invalid: remove(left++); best = max(best, len)
shortest:  for right: add(right); while valid:   best = min(best, len); remove(left++)

3What Goes in the Window State

ConditionState to maintain
sum of windowa running sum
distinct charactersmap char → count (its size = distinct count)
no repeatsset, or map char → last index (lets you jump left)
"contains all of t"need-counts for t + a counter of how many requirements are met
most frequent char in windowcounts + running maxFreq (Longest Repeating Character Replacement)

4The Last-Index Jump Optimization

For "longest substring without repeating characters", store each character's last index. When s[right] was seen inside the window, jump left = lastIndex[s[right]] + 1 instead of shrinking one by one. The complexity stays O(n), but the code is shorter. Remember to only jump forward: left = max(left, last[c] + 1).

Under the HoodWhy It's O(n)▾

Each index enters the window once (when right reaches it) and leaves at most once (when left passes it). The inner while loop's iterations, summed across the whole run, are at most n. So the total work is O(n) amortized, plus O(1) per state update if the state is a hash map or counter. This is the argument interviewers expect when they ask "isn't that nested loop O(n²)?"

⚠️ Common Pitfalls

  1. Using a window when validity isn't monotonic (negative numbers with an exact target sum).
  2. Updating the answer at the wrong time: after shrinking for "longest", inside the shrink loop for "shortest".
  3. Forgetting to delete zero counts from the map, so len(counts) over-reports distinct characters.
  4. Moving left backwards with the last-index jump.
  5. Off-by-one window length: right - left + 1.

📋 Quick Reference

text
Longest valid:  expand right; while invalid → shrink left; record after
Shortest valid: expand right; while valid → record, shrink left
Fixed size k:   window += a[i] - a[i-k]
State: sum · counts map · last-index map · "requirements met" counter
O(n) time · O(k) or O(alphabet) space
Part 2Interview Problems

Six problems: fixed windows, 'longest valid' windows and 'shortest valid' windows, ending with the classic hard Minimum Window Substring.

1Best Time to Buy and Sell Stock (LeetCode 121)

🟢 Easy. prices[i] is a stock's price on day i. Choose one day to buy and a later day to sell; return the maximum profit (0 if none).

text
prices = [7,1,5,3,6,4] → 5   (buy at 1, sell at 6)

Approach. Track the cheapest price so far (the best possible buy day for any sell day). For each day, profit = price − minSoFar. This is a window whose left edge jumps to the newest minimum.

Complexity. O(n) time, O(1) space.

typescript
function maxProfit(prices: number[]): number {
  let minPrice = Infinity, best = 0;
  for (const p of prices) {
    minPrice = Math.min(minPrice, p);
    best = Math.max(best, p - minPrice);
  }
  return best;
}
python
def max_profit(prices):
    min_price = float("inf")
    best = 0
    for p in prices:
        min_price = min(min_price, p)
        best = max(best, p - min_price)
    return best

2Longest Substring Without Repeating Characters (LeetCode 3)

🟠 Medium. Return the length of the longest substring of s with no repeated characters.

text
s = "abcabcbb" → 3   ("abc")

Approach. Variable window with a map from character to its last index. When s[right] already occurs inside the window, jump left past its previous occurrence.

Complexity. O(n) time, O(min(n, alphabet)) space.

typescript
function lengthOfLongestSubstring(s: string): number {
  const last = new Map<string, number>();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if (last.has(c) && last.get(c)! >= left) left = last.get(c)! + 1;
    last.set(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}
python
def length_of_longest_substring(s):
    last = {}
    left = best = 0
    for right, c in enumerate(s):
        if c in last and last[c] >= left:
            left = last[c] + 1
        last[c] = right
        best = max(best, right - left + 1)
    return best

3Longest Repeating Character Replacement (LeetCode 424)

🟠 Medium. You may replace at most k characters of s. Return the length of the longest substring of one repeated letter you can get.

text
s = "AABABBA", k = 1 → 4

Approach. A window is valid when length − maxFreq ≤ k (everything except the most frequent letter gets replaced). Expand right, update counts and maxFreq; while invalid, shrink left. maxFreq never needs to decrease: a smaller maxFreq can't produce a longer answer than one already found.

Complexity. O(n) time, O(26) space.

typescript
function characterReplacement(s: string, k: number): number {
  const counts = new Map<string, number>();
  let left = 0, maxFreq = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    counts.set(s[right], (counts.get(s[right]) ?? 0) + 1);
    maxFreq = Math.max(maxFreq, counts.get(s[right])!);
    while (right - left + 1 - maxFreq > k) {
      counts.set(s[left], counts.get(s[left])! - 1);
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}
python
def character_replacement(s, k):
    counts = {}
    left = max_freq = best = 0
    for right, c in enumerate(s):
        counts[c] = counts.get(c, 0) + 1
        max_freq = max(max_freq, counts[c])
        while (right - left + 1) - max_freq > k:
            counts[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

4Permutation in String (LeetCode 567)

🟠 Medium. Return true if some permutation of s1 appears as a substring of s2.

text
s1 = "ab", s2 = "eidbaooo" → true   ("ba")

Approach. Fixed window of size len(s1) over s2. Keep letter counts for the window and compare with the counts of s1. Sliding adds one letter and removes one, so each step is O(26) (or O(1) with a 'matches' counter).

Complexity. O(26 · n) time, O(26) space.

typescript
function checkInclusion(s1: string, s2: string): boolean {
  const k = s1.length;
  if (k > s2.length) return false;
  const need = new Array(26).fill(0), win = new Array(26).fill(0);
  for (const c of s1) need[c.charCodeAt(0) - 97]++;
  for (let i = 0; i < s2.length; i++) {
    win[s2.charCodeAt(i) - 97]++;
    if (i >= k) win[s2.charCodeAt(i - k) - 97]--;
    if (win.every((v, j) => v === need[j])) return true;
  }
  return false;
}
python
def check_inclusion(s1, s2):
    k = len(s1)
    if k > len(s2):
        return False
    need = [0] * 26
    window = [0] * 26
    for c in s1:
        need[ord(c) - 97] += 1
    for i, c in enumerate(s2):
        window[ord(c) - 97] += 1
        if i >= k:
            window[ord(s2[i - k]) - 97] -= 1
        if window == need:
            return True
    return False

5Minimum Size Subarray Sum (LeetCode 209)

🟠 Medium. Given positive integers nums and target, return the minimal length of a contiguous subarray with sum ≥ target (0 if none).

text
target = 7, nums = [2,3,1,2,4,3] → 2   ([4,3])

Approach. 'Shortest valid' window: expand right adding to the sum; while sum ≥ target, record the length and shrink from the left. Works because all numbers are positive (shrinking always lowers the sum).

Complexity. O(n) time, O(1) space.

typescript
function minSubArrayLen(target: number, nums: number[]): number {
  let left = 0, total = 0, best = Infinity;
  for (let right = 0; right < nums.length; right++) {
    total += nums[right];
    while (total >= target) {
      best = Math.min(best, right - left + 1);
      total -= nums[left++];
    }
  }
  return best === Infinity ? 0 : best;
}
python
def min_sub_array_len(target, nums):
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

6Minimum Window Substring (LeetCode 76)

🔴 Hard. Return the smallest substring of s containing every character of t (with multiplicity), or "".

text
s = "ADOBECODEBANC", t = "ABC" → "BANC"

Approach. Count what t needs. Expand right; when a character's window count reaches its need, increment formed. While formed equals the number of distinct needed characters, the window is valid: record it, then shrink from the left, decrementing formed when a needed count drops below its requirement.

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

typescript
function minWindow(s: string, t: string): string {
  if (!s || !t) return "";
  const need = new Map<string, number>();
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
  const win = new Map<string, number>();
  let formed = 0, left = 0, bestLen = Infinity, bestStart = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    win.set(c, (win.get(c) ?? 0) + 1);
    if (need.has(c) && win.get(c) === need.get(c)) formed++;
    while (formed === need.size) {
      if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestStart = left; }
      const d = s[left++];
      win.set(d, win.get(d)! - 1);
      if (need.has(d) && win.get(d)! < need.get(d)!) formed--;
    }
  }
  return bestLen === Infinity ? "" : s.slice(bestStart, bestStart + bestLen);
}
python
def min_window(s, t):
    if not t or not s:
        return ""
    need = {}
    for c in t:
        need[c] = need.get(c, 0) + 1
    window = {}
    formed, required = 0, len(need)
    left = 0
    best_len, best_start = float("inf"), 0
    for right, c in enumerate(s):
        window[c] = window.get(c, 0) + 1
        if c in need and window[c] == need[c]:
            formed += 1
        while formed == required:
            if right - left + 1 < best_len:
                best_len, best_start = right - left + 1, left
            d = s[left]
            window[d] -= 1
            if d in need and window[d] < need[d]:
                formed -= 1
            left += 1
    return "" if best_len == float("inf") else s[best_start:best_start + best_len]

🧠 Key takeaways

  • Use a window for contiguous ranges when validity is monotonic.
  • Longest: shrink while invalid, record after. Shortest: record and shrink while valid.
  • Keep window state incrementally: running sum, counts map, last index, 'formed' counter.
  • Each index enters and leaves once → O(n) despite the inner loop.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

#1
algo_sliding_window_exercise_1.py
TSPY
#2
algo_sliding_window_exercise_2.py
TSPY

✅ Check yourself

Answer the questions — feedback is instant.

1. Why can't a sliding window solve 'subarray sum equals k' with negative numbers?
Use prefix sums + hash map.
2. In 'shortest valid window' problems, when do you record the answer?
Valid windows get shorter as you shrink.
3. Longest Repeating Character Replacement's validity check is…
Replace everything except the majority letter.
4. Complexity of the Minimum Window Substring solution?
Two forward pointers.

Source: algo_sliding_window_theory_1.md, algo_sliding_window_theory_2.md · generated by tools/build_lessons.py