Minimum Window Substring

You are given two strings s and t. Find the shortest contiguous substring of s that contains every character of t, including repeats: if t contains a letter three times, the substring must contain it at least three times. The characters may appear in any order and other characters may sit between them.

Return that substring. If no substring of s qualifies, return the empty string "". If several shortest substrings exist, return the one that starts earliest in s.

Letters are case-sensitive: 'a' and 'A' are different characters.

Example 1

Example 2

Example 3

Constraints

• 1 <= s.length, t.length <= 105
• s and t contain only English letters (upper and lower case).

Pattern Path · Sliding Window · problem 55 of 169

Start simple

Check every substring and compare its letter counts with t's: O(n² · k) time, or O(n²) with incremental counts.

The key idea

Use a sliding window s[left..right] together with a count of how many characters of t it still lacks.

• Keep need[c]: how many more copies of c the window requires (it can go negative when the window has extras), and missing: the total still required, starting at len(t).
• Move right one step at a time. If the new character was still needed (need[c] > 0), missing drops by one. Either way, decrement need[c].
• Whenever missing == 0 the window is valid. Record it if it is the shortest so far, then advance left, giving the character back to need. Once a needed character is given up, missing rises and you go back to growing.

Why it is correct: for each right end, shrinking finds the latest left end that still works, which is the shortest valid window ending there. Taking the best over every right end covers every candidate. Both pointers only move forward, so the total work is linear. A tie keeps the earlier window because we only replace the answer on a strictly shorter length.

Complexity

• Time: O(|s| + |t|)
• Space: O(k) for k distinct characters

Python

from collections import Counter


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = Counter(t)       # copies of each char the window still needs
        missing = len(t)        # total chars of t not yet covered
        best_start, best_len = 0, float("inf")
        left = 0
        for right, ch in enumerate(s):
            if need[ch] > 0:
                missing -= 1
            need[ch] -= 1
            # The window covers t: shrink it from the left while it still does.
            while missing == 0:
                if right - left + 1 < best_len:
                    best_start, best_len = left, right - left + 1
                need[s[left]] += 1
                if need[s[left]] > 0:
                    missing += 1
                left += 1
        if best_len == float("inf"):
            return ""
        return s[best_start:best_start + best_len]

JavaScript

var minWindow = function(s, t) {
  const need = new Map();   // copies of each char the window still needs
  for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);
  let missing = t.length;   // total chars of t not yet covered
  let bestStart = 0, bestLen = Infinity;
  let left = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if ((need.get(ch) || 0) > 0) missing--;
    need.set(ch, (need.get(ch) || 0) - 1);
    // The window covers t: shrink it from the left while it still does.
    while (missing === 0) {
      if (right - left + 1 < bestLen) {
        bestStart = left;
        bestLen = right - left + 1;
      }
      const out = s[left];
      need.set(out, need.get(out) + 1);
      if (need.get(out) > 0) missing++;
      left++;
    }
  }
  return bestLen === Infinity ? "" : s.slice(bestStart, bestStart + bestLen);
};

What the interviewer is checking

This is the canonical variable-size sliding window. The interviewer is checking that you can maintain a validity condition in O(1) per step instead of recounting, and that you handle repeated characters correctly.

Mistakes to avoid

• Treating t as a set of letters and ignoring how many times each one appears.
• Comparing whole count tables on every step, which multiplies the running time by the alphabet size.
• Decrementing missing for surplus copies of a letter the window already has enough of.
• Off-by-one errors when recording the window length (right - left + 1).

Follow-ups to expect

• What if the characters of t must appear in order? (DP or two-pass subsequence scan.)
• Can you skip characters that are not in t? (Filter s to relevant positions.)
• Find the longest substring with at most k distinct characters. (Same window, different condition.)

In real software

Search engines build result snippets by finding the shortest passage that mentions every query term, and log analysers look for the tightest time span containing a set of required events.

Practice next