Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Minimum Window Substring

Find the shortest substring that contains every character of a pattern, repeats included, with a sliding window and a count of what is still missing.

Updated Medium read: 7 min read

Approaches at a glance

ApproachTimeSpace
Brute forceO(n·(n + m))O(m)
Sliding window with a missing counterO(n + m)O(m)

The problem

Given a text and a pattern, return the shortest substring of the text that contains every character of the pattern. Repeats count: if the pattern has two as, the substring needs at least two as. The order of the characters does not matter, and the substring may contain extra characters. If no substring qualifies, return an empty string.

text = "ADOBECODEBANC", pattern = "ABC"   →  "BANC"
text = "a",             pattern = "a"     →  "a"
text = "a",             pattern = "aa"    →  ""     (only one a available)

Upper and lower case are different characters. In the complexity figures, n is the length of the text and m is the length of the pattern.

Approach 1: brute force

From every starting position, extend to the right until the pattern is covered, and keep the shortest result.

To know when the pattern is covered, keep a map of how many of each character are still needed, and a single number, missing, for how many characters are needed in total.

JavaScript

function minWindowBruteForce(text, pattern) {
  if (pattern.length === 0) return "";
  let best = "";
 
  for (let start = 0; start < text.length; start++) {
    const need = new Map();
    for (const ch of pattern) need.set(ch, (need.get(ch) ?? 0) + 1);
    let missing = pattern.length;
 
    for (let end = start; end < text.length; end++) {
      const ch = text[end];
      if (need.get(ch) > 0) missing--;
      if (need.has(ch)) need.set(ch, need.get(ch) - 1);
 
      if (missing === 0) {
        if (best === "" || end - start + 1 < best.length) {
          best = text.slice(start, end + 1);
        }
        break;
      }
    }
  }
  return best;
}

Python

from collections import Counter
 
def min_window_brute_force(text, pattern):
    if not pattern:
        return ""
    best = ""
 
    for start in range(len(text)):
        need = Counter(pattern)
        missing = len(pattern)
 
        for end in range(start, len(text)):
            ch = text[end]
            if ch in need:
                if need[ch] > 0:
                    missing -= 1
                need[ch] -= 1
 
            if missing == 0:
                if best == "" or end - start + 1 < len(best):
                    best = text[start : end + 1]
                break
    return best

Time O(n·(n + m)): for each of n starts, the map is rebuilt from the pattern and up to n characters are scanned. Space O(m) for the map.

Approach 2: sliding window

The brute force starts from nothing at every position. A sliding window keeps the map and the counter alive and updates them as the window's two ends move.

  1. Move end to the right, taking characters into the window, until nothing is missing.
  2. The window now covers the pattern. Record it if it is the shortest so far, then drop the character at start and move start up. Repeat while the window still covers the pattern.
  3. As soon as something is missing again, go back to step 1.

This is the "shrink while valid" shape used in Minimum Size Subarray Sum. The only new part is the bookkeeping for what "valid" means.

The bookkeeping

need maps each pattern character to how many more of it the window requires. The trick that keeps everything simple is to let these numbers go negative:

Value in need Meaning
Positive The window is short of this character by that many
Zero The window has exactly as many as the pattern asks for
Negative The window has that many spare

missing is the total of the positive values. It only changes when a character genuinely fills a gap or opens one:

  • Taking a character in: if its need is above zero, it filled a gap, so missing goes down. Then its need goes down by one either way.
  • Letting a character go: its need goes up by one. If that makes it positive, a gap has opened, so missing goes up.

The window covers the pattern exactly when missing is zero: one number to check, instead of comparing two maps.

JavaScript

function minWindow(text, pattern) {
  if (pattern.length === 0 || pattern.length > text.length) return "";
 
  const need = new Map();
  for (const ch of pattern) need.set(ch, (need.get(ch) ?? 0) + 1);
 
  let missing = pattern.length;
  let start = 0;
  let bestStart = 0;
  let bestLength = Infinity;
 
  for (let end = 0; end < text.length; end++) {
    const added = text[end];
    if (need.has(added)) {
      if (need.get(added) > 0) missing--;
      need.set(added, need.get(added) - 1);
    }
 
    while (missing === 0) {
      if (end - start + 1 < bestLength) {
        bestStart = start;
        bestLength = end - start + 1;
      }
 
      const removed = text[start];
      if (need.has(removed)) {
        need.set(removed, need.get(removed) + 1);
        if (need.get(removed) > 0) missing++;
      }
      start++;
    }
  }
 
  if (bestLength === Infinity) return "";
  return text.slice(bestStart, bestStart + bestLength);
}

Python

from collections import Counter
 
def min_window(text, pattern):
    if not pattern or len(pattern) > len(text):
        return ""
 
    need = Counter(pattern)
    missing = len(pattern)
    start = 0
    best_start = 0
    best_length = float("inf")
 
    for end, added in enumerate(text):
        if added in need:
            if need[added] > 0:
                missing -= 1
            need[added] -= 1
 
        while missing == 0:
            if end - start + 1 < best_length:
                best_start = start
                best_length = end - start + 1
 
            removed = text[start]
            if removed in need:
                need[removed] += 1
                if need[removed] > 0:
                    missing += 1
            start += 1
 
    if best_length == float("inf"):
        return ""
    return text[best_start : best_start + best_length]

Characters that are not in the pattern are never put in the map. They pass through the window without touching the counts.

Walkthrough

text = "ADOBECODEBANC", pattern = "ABC". Only the steps where something happens are shown:

end (char) Window when valid What shrinking does Best so far
0 (A) to 4 (E) Not valid yet: C is missing none
5 (C) "ADOBEC" Record length 6. Drop A: now A is missing "ADOBEC"
6 (O) to 9 (B) Not valid: A is missing. The B at index 9 is a spare "ADOBEC"
10 (A) "DOBECODEBA" Drop D, O. Drop B: fine, there is a spare. Drop E. "CODEBA" is length 6, no better. Drop C: now C is missing "ADOBEC"
11 (N) Not valid: C is missing "ADOBEC"
12 (C) "ODEBANC" Drop O, D: "EBANC" is length 5. Drop E: "BANC" is length 4. Drop B: now B is missing "BANC"

The row for index 10 shows why negative counts are useful. By then the window holds two Bs, so need for B is −1. Dropping the first B takes it back to 0, which is not positive, so missing stays at zero and the window is correctly still valid.

Time O(n + m): building the map takes m steps, and each character of the text enters the window once and leaves at most once. Space O(m): the map holds at most one entry per distinct pattern character.

Why no shorter window is skipped

For each position of end, the inner loop moves start as far right as it can go while the window stays valid, so it finds the shortest valid window ending at that position. Every substring ends somewhere, so the overall shortest is among the ones recorded.

start never needs to move back. If a window from start to end is missing something, a window from start to any earlier end is missing it too, so the positions start has passed are finished with for good.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(minWindow("ADOBECODEBANC", "ABC")); // "BANC"
console.log(minWindow("a", "aa")); // ""

Python

print(min_window("ADOBECODEBANC", "ABC"))  # "BANC"
print(min_window("a", "aa"))  # ""

The comment after each line is the result you should see.

Common mistakes

  • Tracking only which characters are present. A set cannot tell one a from two. Pattern "aa" against text "a" must return "".
  • Decreasing missing for every pattern character seen. A third B when the pattern wants one does not fill a gap. Only decrease when need was above zero.
  • Stopping the counts at zero. Without negative values there is no record of spares, and dropping a spare character looks like opening a gap.
  • Recording the window after shrinking it. Record first, while it is still valid, then drop the front character.
  • Building a substring on every improvement. Storing the start and length and slicing once at the end avoids copying text repeatedly.

Original problem: LeetCode 76: Minimum Window Substring