Minimum Window Substring (Characters)

1function minWindow(text: string, required: string): string {
2    if (required.length === 0) return "";
3  
4    const need: Record<string, number> = {};
5    for (const ch of required) need[ch] = (need[ch] ?? 0) + 1;
6  
7    let missing = required.length; // total characters still missing (including duplicates)
8    let left = 0;
9  
10    let bestStart = 0;
11    let bestLen = Infinity;
12  
13    for (let right = 0; right < text.length; right++) {
14      const ch = text[right];
15  
16      if (need[ch] !== undefined) {
17        if (need[ch] > 0) missing--;
18        need[ch]--;
19      }
20  
21      // when missing == 0, window is valid; try shrinking from the left
22      while (missing === 0) {
23        const windowLen = right - left + 1;
24        if (windowLen < bestLen) {
25          bestLen = windowLen;
26          bestStart = left;
27        }
28  
29        const leftCh = text[left];
30        if (need[leftCh] !== undefined) {
31          need[leftCh]++;
32          if (need[leftCh] > 0) missing++; // we now miss one required char
33        }
34        left++;
35      }
36    }
37  
38    return bestLen === Infinity ? "" : text.slice(bestStart, bestStart + bestLen);
39  }
40
41console.log(minWindow("ADOBECODEBANC", "ABC")); // "BANC"
42