find the smallest window in a string containing all characters of another string
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: ""
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);}