M.A.T.R.I.X

Appearance

Volume ITechnology

4.6.5 — Minimum Window Substring ​

LeetCode 76 · Hard · ★ Blind 75

The problem ​

Return the shortest substring of s that contains every character of t, including repeats. Return "" if there is none.

s = "ADOBECODEBANC", t = "ABC"   →  "BANC"
s = "a", t = "aa"                →  ""     (only one a available, two needed)

Both strings may contain any English letters, upper or lower case. Up to 100,000 characters.

"Including repeats" is the detail that decides the solution. If t is "AABC" the window needs two A's, not one. That is why this is a counting problem and not a set problem.

Constraints:

  • Length of s and t \le 100,000.
  • Answers are guaranteed to be unique if they exist.

Plain English: Find the smallest possible slice of s that contains every single character from t in the correct quantities.

The naive approach ​

The brute-force way is to check every possible substring of s. For each substring, count its characters and compare them against t's counts.

  • Why it fails: Generating all substrings takes O(n^2). Counting characters takes O(n). Total time is O(n^3). With n = 100,000, this will definitely TLE.

The pattern ​

Same window as before, but the target has flipped. Previous problems wanted the longest window satisfying a condition, so you recorded the answer after repairing an invalid window. Here you want the shortest valid window, so:

  • Extend the right edge until the window becomes valid.
  • Then shrink from the left as long as it stays valid, recording the answer each time.
  • Stop shrinking the moment it breaks, and go back to extending.

The shape is the mirror image: grow until valid, then shrink while still valid.

The ELI5 Analogy: Imagine you are shopping for a very specific recipe that needs 2 apples, 1 banana, and 1 carrot. You walk down a massive conveyor belt of random groceries (this is s). You just keep grabbing items (expanding right) until your basket finally has enough of what you need. At that exact moment, you stop grabbing. Now, you look at the first thing you grabbed (the left edge). If it's a random box of cereal, or an extra third apple you don't actually need, you throw it out (shrink from the left). You keep throwing things out until throwing out one more item would ruin your recipe. That trimmed basket is your best attempt so far. Then you start grabbing new items again to see if you can find a smaller cluster further down the belt.

Tracking validity without rechecking everything ​

The naive check is "does the window contain enough of every character in t", which costs O(52) per step. There is a cleaner way that costs O(1), and it is the idea worth taking from this problem.

Keep two numbers:

  • required — how many distinct characters of t still need their full count met.
  • For each character, how many the window currently holds.

When a character's window count reaches exactly its required count, one requirement is satisfied, so required drops by one. When it falls below again, required goes back up.

The window is valid exactly when required == 0. One integer comparison.

The word exactly is doing real work. If the window holds three A's and needs two, adding a fourth changes nothing about validity, so required must not move. Only the transition through the boundary counts.

The solution ​

python
from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t or len(t) > len(s):
            return ""

        need = Counter(t)
        required = len(need)          # distinct characters still unsatisfied
        window = {}

        left = 0
        best_len = float('inf')
        best_start = 0

        for right in range(len(s)):
            c = s[right]
            window[c] = window.get(c, 0) + 1
            if c in need and window[c] == need[c]:      # exactly met
                required -= 1

            while required == 0:                        # valid — try to shrink
                if right - left + 1 < best_len:
                    best_len = right - left + 1
                    best_start = left

                lc = s[left]
                window[lc] -= 1
                if lc in need and window[lc] < need[lc]:   # just broke it
                    required += 1
                left += 1

        return "" if best_len == float('inf') else s[best_start:best_start + best_len]
ts
function minWindow(s: string, t: string): string {
  if (!s || !t || t.length > s.length) return "";

  const need = new Map<string, number>();
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);

  let required = need.size;
  const window = new Map<string, number>();

  let left = 0, bestLen = Infinity, bestStart = 0;

  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)) required--;

    while (required === 0) {
      if (right - left + 1 < bestLen) {
        bestLen = right - left + 1;
        bestStart = left;
      }
      const lc = s[left];
      window.set(lc, window.get(lc)! - 1);
      if (need.has(lc) && window.get(lc)! < need.get(lc)!) required++;
      left++;
    }
  }

  return bestLen === Infinity ? "" : s.slice(bestStart, bestStart + bestLen);
}

Code Walkthrough ​

  • required = len(need): The number of unique characters we need to fulfill.
  • if c in need and window[c] == need[c]: required -= 1: As the right pointer grabs items, we check if we just perfectly satisfied the requirement for character c. If so, we have one less unique character to worry about.
  • while required == 0:: This loop only runs when our basket has everything we need.
  • if right - left + 1 < best_len:: We record the size of the basket before we start throwing things out, keeping it if it's our new personal best.
  • window[lc] -= 1: We throw out the leftmost item.
  • if lc in need and window[lc] < need[lc]: required += 1: If the item we threw out was essential to our recipe, our basket is no longer valid. required goes up, which breaks the while loop and forces us to start grabbing new items with the right pointer again.

Four things to notice.

required counts distinct characters, not total characters. For t = "AABC" it starts at 3, not 4, because there are three distinct letters. Getting this wrong is the most common bug in this problem.

window[c] == need[c] uses ==, not >=. Only the exact moment of satisfying a requirement should decrement required. Using >= would decrement again on every extra copy.

window[lc] < need[lc] uses <, mirroring it. Only the moment of dropping below breaks the requirement.

The answer is recorded inside the shrink loop, before shrinking. At that instant the window is valid, and every further shrink either keeps it valid — in which case it is recorded again, smaller — or breaks it. So every valid window is measured.

Storing best_start and best_len rather than slicing the string each time matters: slicing inside the loop would be O(n) per step and would quietly make the whole solution quadratic. This is the "track index pairs, do not cut substrings" discipline from 4.2.

Trace ​

s = "ADOBECODEBANC", t = "ABC", so need = {A:1, B:1, C:1} and required = 3.

eventwindowrequiredbest
right reaches C at index 5ADOBEC0"ADOBEC" (6)
shrink: drop ADOBEC1—
right reaches A at index 10DOBECODEBA0still 6, this is longer
shrink to ODEBA… then to BANC later"BANC" (4)

The final answer is "BANC".

Edge cases ​

  • t is longer than s: Handled by the first if statement. Impossible to satisfy.
  • t has characters not in s: The required counter will never hit 0, and the while loop will never run. Returns "".
  • Exact match: s = "a", t = "a". The right loop runs once, required hits 0, best_len becomes 1, the left pointer moves, required goes up to 1, loop ends, returns "a".

Complexity ​

O(n + m) time. Each pointer moves forward at most n times over the entire run, and every other operation is O(1) thanks to the required counter.

O(m) space for the two maps, where m is the number of distinct characters in t.

Where this goes next ​

This is the reference implementation for the shortest valid window family:

  • Minimum Size Subarray Sum — the shortest subarray with sum at least k, for positive numbers. Same skeleton, validity is a running sum.
  • Substring with Concatenation of All Words — the same counting idea over whole words instead of characters.
  • Smallest Range Covering Elements from K Lists — the same "cover everything, then shrink" idea across several sorted lists, using a heap.

The general rule, and it is worth memorising as a pair:

  • Longest valid window: shrink while invalid, record after the loop.
  • Shortest valid window: shrink while valid, record inside the loop.

Knowing which one a problem is asking for, before you write anything, is most of the battle.

What the interviewer will push on ​

"Why does required count distinct characters?" Because one character's requirement is satisfied once, no matter how many copies it needs. Counting total characters would need a different update rule and gets tangled fast.

"Why == and not >= when decrementing?" So that extra copies beyond the requirement do not decrement it again.

"Prove this is O(n)." Both pointers only move forward and never pass each other, so together they take at most 2n steps.

"What if t has duplicate characters?" It already works — that is exactly what the counts handle. This question is checking whether you used a set instead of a counting map.

"Can you return the window without slicing inside the loop?" Yes, and you should: store the start index and length, slice once at the end.

One thing to volunteer: state the two window shapes before coding. "For the longest window I shrink while invalid; for the shortest I shrink while valid and record inside the loop. This is the second one." That framing tells the interviewer you have a method rather than a memorised solution.

Next: 4.6.6 Sliding Window Maximum — a fixed window again, but now you must know its maximum at every step, which needs a different structure entirely.