Minimum Window Substring

Examples

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

"BANC" contains one A, one B, and one C — the minimum-length window in s that covers all of "ABC".

Input: s = "a", t = "a"
Output: "a"

The whole string already matches exactly.

Input: s = "a", t = "aa"
Output: ""

t needs two a's, but s only has one, so no valid window exists.

Constraints

• 1 <= s.length, t.length <= 10^5

• s and t consist of English letters (upper and/or lower case).

• There is guaranteed to be at least one valid answer, or the correct result is an empty string.

Approach

The brute-force approach checks every possible substring of s, and for each one verifies whether it contains enough of every character required by t. That means re-scanning overlapping substrings again and again, and doing a full comparison against t's requirements each time.

A sliding window is far more efficient. Keep a count of how many of each character t requires, and a matching count for what the current window actually has. Grow the window from the right, and every time a character reaches exactly the count t needs for it, mark one more requirement as "satisfied." Once all requirements are satisfied, the window is valid — at that point, try shrinking it from the left as far as possible (each shrink might record a new best answer) until it becomes invalid again (a requirement drops below what's needed). Then resume growing from the right. Tracking a single "how many requirements are satisfied" counter, rather than re-checking every character's count each time, keeps each step of the process fast — every character is added to and removed from the window at most once overall.

Solutions

Brute Force — Check Every Substring

For every possible start and end position, build the substring's character counts and check whether it covers every requirement of t, tracking the shortest one that works.

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

  const need = buildCounts(t);
  let best = "";

  for (let start = 0; start < s.length; start++) {
    const have = {};
    for (let end = start; end < s.length; end++) {
      have[s[end]] = (have[s[end]] || 0) + 1;

      if (covers(need, have)) {
        const candidate = s.slice(start, end + 1);
        if (best === "" || candidate.length < best.length) {
          best = candidate;
        }
        break; // no need to extend this start further once it's valid
      }
    }
  }

  return best;
}

function buildCounts(str) {
  const counts = {};
  for (const ch of str) counts[ch] = (counts[ch] || 0) + 1;
  return counts;
}

function covers(need, have) {
  for (const ch in need) {
    if ((have[ch] || 0) < need[ch]) return false;
  }
  return true;
}

Time: O(n² * k) — n² substrings in the worst case, k = distinct characters in t for each coverage check · Space: O(k) for the character count maps

Optimal — Sliding Window with a Satisfied-Count

Grow the window until every character requirement from t is met, tracked with a single counter instead of rechecking all counts. Then shrink from the left as far as possible, recording the best window at each valid point, before growing again.

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

  const need = {};
  for (const ch of t) need[ch] = (need[ch] || 0) + 1;
  const required = Object.keys(need).length;

  const have = {};
  let satisfied = 0;
  let left = 0;
  let bestLen = Infinity;
  let bestStart = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    have[ch] = (have[ch] || 0) + 1;

    if (need[ch] !== undefined && have[ch] === need[ch]) {
      satisfied++;
    }

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

      const leftChar = s[left];
      have[leftChar]--;
      if (need[leftChar] !== undefined && have[leftChar] < need[leftChar]) {
        satisfied--;
      }
      left++;
    }
  }

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

Time: O(n + m) — n = s.length, m = t.length; each index enters and leaves the window at most once · Space: O(k) — k = distinct characters in t