minimum-window-substring.ts

/**
 * 76. Minimum Window Substring  (Hard)
 * Link: https://leetcode.com/problems/minimum-window-substring/
 *
 * Given strings `s` and `t`, return the shortest substring of `s` that contains
 * every character of `t` (including multiplicities), or "" if none exists.
 *
 * Example:
 *   Input:  s = "ADOBECODEBANC", t = "ABC"
 *   Output: "BANC"
 *
 * Approach:
 *   Sliding window with a need-count map for `t` and a `missing` counter of how
 *   many required characters are still unmet. Expand the right edge, decrementing
 *   missing when a needed char is covered. Once missing hits 0, contract from the
 *   left to shrink the window while it stays valid, recording the best.
 *
 * Time:  O(|s| + |t|)
 * Space: O(|t|)
 */
export function minWindow(s: string, t: string): string {
  if (t.length === 0 || s.length < t.length) return "";

  const need = new Map<string, number>();
  for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);

  let missing = t.length;
  let left = 0;
  let bestLen = Infinity;
  let bestStart = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if ((need.get(ch) ?? 0) > 0) missing--;
    need.set(ch, (need.get(ch) ?? 0) - 1);

    while (missing === 0) {
      if (right - left + 1 < bestLen) {
        bestLen = right - left + 1;
        bestStart = left;
      }
      const leftCh = s[left];
      need.set(leftCh, (need.get(leftCh) ?? 0) + 1);
      if ((need.get(leftCh) ?? 0) > 0) missing++;
      left++;
    }
  }

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