find the smallest window in a string containing all characters of another string

Hard

Problem

Given strings s and t, return the shortest substring of s that contains every character of t, counting duplicates. Return "" if there is no such window.

Example 1

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

Example 2

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

t needs two a’s, but s has only one.

Also asked as: minimum window substring · smallest window that contains all characters of string itself

Test cases

Case 1

Input:    "ADOBECODEBANC", "ABC"
Expected: "BANC"

Case 2

Input:    "a", "a"
Expected: "a"

Case 3

Input:    "a", "aa"
Expected: ""

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Sliding window with need-count

Time O(n)Space O(k)

Expand right until the window covers all needed chars, then contract left while it still does, tracking the smallest.

function minWindow(s, t) {
const need = new Map();
for (const c of t) need.set(c, (need.get(c) || 0) + 1);
let missing = t.length, start = 0, resStart = 0, resLen = Infinity;
for (let end = 0; end < s.length; end++) {
const c = s[end];
if (need.get(c) > 0) missing--;
need.set(c, (need.get(c) || 0) - 1);
while (missing === 0) {
if (end - start + 1 < resLen) { resLen = end - start + 1; resStart = start; }
const lc = s[start++];
need.set(lc, need.get(lc) + 1);
if (need.get(lc) > 0) missing++;
}
}
return resLen === Infinity ? '' : s.slice(resStart, resStart + resLen);
}