Minimum Window Substring

HardSliding WindowHash TableStringSliding Window

Problem

You are given a source string and a target string. Find the shortest contiguous substring of the source that contains every character of the target, including matching each character's required count if it appears more than once. Return an empty string if no such substring exists.

Example. For source "ADOBECODEBANC" and target "ABC", the shortest qualifying substring is "BANC".

Key idea

Testing every substring of the source against the target's requirements is expensive to repeat from scratch. A variable-size sliding window handles it in one pass. First tally how many of each character the target needs. Then expand the window's right edge through the source, updating a count of characters collected so far, and track how many of the target's distinct required characters currently have their need fully met. Once every requirement is met, the window is valid: shrink it from the left as far as possible while it stays valid, recording the shortest window seen. Then resume expanding the right edge to search for the next valid window, repeating until the source is exhausted.

Solution

function minWindow(s: string, t: string): string {
  if (t.length === 0 || s.length < t.length) {
    return '';
  }

  const required = new Map<string, number>();
  for (const char of t) {
    required.set(char, (required.get(char) ?? 0) + 1);
  }

  const windowCounts = new Map<string, number>();
  let satisfied = 0;
  const needed = required.size;

  let bestStart = 0;
  let bestLength = Infinity;
  let left = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    windowCounts.set(char, (windowCounts.get(char) ?? 0) + 1);

    // mark this character's requirement as met the moment the count matches
    if (required.has(char) && windowCounts.get(char) === required.get(char)) {
      satisfied++;
    }

    // every requirement is covered, so shrink the window as far as it stays valid
    while (satisfied === needed) {
      if (right - left + 1 < bestLength) {
        bestLength = right - left + 1;
        bestStart = left;
      }

      const leftChar = s[left];
      windowCounts.set(leftChar, (windowCounts.get(leftChar) ?? 0) - 1);
      if (required.has(leftChar) && windowCounts.get(leftChar)! < required.get(leftChar)!) {
        satisfied--;
      }

      left++;
    }
  }

  return bestLength === Infinity ? '' : s.slice(bestStart, bestStart + bestLength);
}

Complexity

  • Time: O(|source| + |target|). The right and left pointers each move forward across the source at most once in total, after an initial O(|target|) setup.
  • Space: O(|target|). For the map of required character counts, plus a similarly small map for the window's own counts.

Watch out for

  • The target may repeat a character, so its required count for that character must be tracked as a number, not just presence or absence.
  • Only mark a character's requirement as "met" the moment its window count reaches its required count; going past that point should not be counted again.
  • Shrink the window only while it stays fully valid; shrinking one step too far invalidates it and must be checked before, not after, recording a candidate answer.

Pattern

This is the variable-size sliding window with a "satisfy every requirement" validity rule, the same expand-then-contract template used in Longest Substring Without Repeating Characters and Longest Repeating Character Replacement, adapted to a multi-character coverage condition instead of a single count threshold.

Related questions