Minimum Window Substring

1. Define the problem

Given two strings s and t, find the smallest substring of s that contains every character of t (including duplicates). Grow a window until it is valid, then shrink from the left while it stays valid. Return "" if no such window exists.

Constraints

1 ≤ s.length, t.length ≤ 10⁵
s and t consist of uppercase and lowercase English letters

Example

Inputs = "ADOBECODEBANC", t = "ABC"

Output"BANC"

Explanation BANC is the shortest substring of s that covers A, B, and C.

2. Know the words first

In plain terms

Substring: A run of characters taken right out of the string as-is, next to each other in order — not letters picked out from anywhere, that's a different thing (a subsequence).

3. Visualize the solution

Shrink to the minimum covering window

10A

11N

12C

StatusValid

First time have === required: window "ADOBEC" covers ABC (len 6).

What happens in this step

window = [0, 5]  "ADOBEC"
have = 3 / required = 3   (need: A:1, B:1, C:1)

window map: {A:1, D:1, O:1, B:1, E:1, C:1}

Adding C at index 5 makes have hit required for the first time — every character of t is now covered. bestLen = 6.

Step 1 of 4

Steps to visualize

Grow right and update window counts until every required character from t is covered.
Once have equals required, the window is valid — record its length if smaller.
Shrink left while the window stays valid, chasing a shorter covering substring.
When shrinking breaks coverage, grow right again to restore it.
Return the best slice, or empty if no covering window exists.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Shrink to the minimum covering window

10A

11N

12C

StatusValid

First time have === required: window "ADOBEC" covers ABC (len 6).

What happens in this step

window = [0, 5]  "ADOBEC"
have = 3 / required = 3   (need: A:1, B:1, C:1)

window map: {A:1, D:1, O:1, B:1, E:1, C:1}

Adding C at index 5 makes have hit required for the first time — every character of t is now covered. bestLen = 6.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function minWindow(s, t) {
  if (s.length === 0 || t.length === 0 || t.length > s.length) return "";

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

  const required = need.size;
  let have = 0;
  const window = new Map();

  let left = 0;
  let bestLen = Infinity;
  let 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)) {
      have++;
    }

    while (have === required) {
      if (right - left + 1 < bestLen) {
        bestLen = right - left + 1;
        bestStart = left;
      }

      const leftChar = s[left];
      window.set(leftChar, window.get(leftChar) - 1);
      if (need.has(leftChar) && window.get(leftChar) < need.get(leftChar)) {
        have--;
      }
      left++;
    }
  }

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

Time: O(|s| + |t|)
Space: O(|t|)

6. Test cases

Test cases

Input	Expected	Covers
`s = "ADOBECODEBANC", t = "ABC"`	`"BANC"`	Docstring example
`s = "", t = "ABC"`	`""`	Empty s returns empty string
`s = "ABC", t = ""`	`""`	Empty t returns empty string
`s = "a", t = "aa"`	`""`	No valid window exists
`s = "abc", t = "xyz"`	`""`	No overlapping alphabet
`s = "a", t = "a"`	`"a"`	Single character match
`s = "aa", t = "aa"`	`"aa"`	Entire string is the answer
`s = "a", t = "aaa"`	`""`	t longer than s
`s = "aaflslflsldkalskaaa", t = "aa"`	`"aa"`	Duplicate required characters
`s = "aabdccdbcacd", t = "cbd"`	`"bdc"`	Larger hand-verified case
`s = "cabwefgewcwaefgcf", t = "cae"`	`"cwae"`	Another larger hand-verified case

Minimum Window Substring