Minimum window substring

Hard TimeO(n) SpaceO(k)

Given strings s and t, return the shortest substring of s that holds every character of t, counting repeats, or the empty string "" when no substring does. A character t asks for twice must appear twice in the answer. The answer may hold characters t does not ask for — only its length matters — and where two substrings tie for shortest, either is correct.

Examples

Example 1

Input
s = "ADOBECODEBANC"t = "ABC"
Output
"BANC"
Four characters holding B, A and C; the first window that worked, "ADOBEC", needed six.

Example 2

Input
s = "a"t = "aa"
Output
""
t asks for two a and s holds one, so no substring can cover it.

The Code

function minWindow(s, t) {
  const need = new Map();
  for (let i = 0; i < t.length; i++) {
    need.set(t[i], (need.get(t[i]) || 0) + 1);
  }
  let missing = t.length;
  let start = 0;
  let bestStart = 0;
  let bestLength = -1;
  for (let end = 0; end < s.length; end++) {
    const ch = s[end];
    if (need.has(ch)) {
      if (need.get(ch) > 0) missing--;
      need.set(ch, need.get(ch) - 1);
    }
    while (missing === 0) {
      if (bestLength === -1 || end - start + 1 < bestLength) {
        bestLength = end - start + 1;
        bestStart = start;
      }
      const left = s[start];
      if (need.has(left)) {
        need.set(left, need.get(left) + 1);
        if (need.get(left) > 0) missing++;
      }
      start++;
    }
  }
  return bestLength === -1 ? "" : s.slice(bestStart, bestStart + bestLength);
}
minWindow("ADOBECODEBANC", "ABC");
Done

The first 14 calls, of 32. This one does not fit on a page.

Step through minWindow("ADOBECODEBANC", "ABC") call by call

More like this

All strings examples (13) →