Minimum Window Substring

找出包含 t 全部字符的最小子串。

找出 s 中包含 t 全部字符且频次也满足要求的最小子串。真正的难点不是找到一个合法窗口，而是在不丢覆盖的前提下把它缩到最短。

StringSliding Window

题目定位

这是最经典的覆盖型窗口：先扩张到完全覆盖，再在仍合法的前提下尽量收缩。

关键观察

核心状态不是简单的不同字符个数，而是“有多少种必需字符的需求频次已经被完全满足”。

目标复杂度

O(n) / O(k)

这题的解法思路怎么拆

先为 t 建一个频次表，明确每个字符需要满足多少次。

右指针扩张时，把对应字符的需求量减一。

当全部需求都满足后，就尽可能右移左指针，把窗口缩到仍然合法的最短状态。

每次窗口合法时，都拿它和当前最优答案比较。

拿一个例子顺一遍

例如 s = "ADOBECODEBANC", t = "ABC"。

第一次找到的合法窗口是 "ADOBEC"，但它还不是最短。

继续扩张和收缩，直到找到窗口 "BANC"。

此时已经不存在更短的合法窗口，所以答案就是 "BANC"。

参考实现

Python

from collections import Counter

def minWindow(s: str, t: str) -> str:
    need = Counter(t)
    missing = len(t)
    left = 0
    best_start = 0
    best_len = float("inf")

    for right, char in enumerate(s):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1

        while missing == 0:
            if right - left + 1 < best_len:
                best_start = left
                best_len = right - left + 1

            left_char = s[left]
            need[left_char] += 1
            if need[left_char] > 0:
                missing += 1
            left += 1

    if best_len == float("inf"):
        return ""

    return s[best_start:best_start + best_len]

TypeScript 版本

TypeScript

function minWindow(s: string, t: string): string {
  const need = new Map<string, number>();
  for (const char of t) {
    need.set(char, (need.get(char) ?? 0) + 1);
  }

  let missing = t.length;
  let left = 0;
  let bestStart = 0;
  let bestLength = Number.POSITIVE_INFINITY;

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

    while (missing === 0) {
      if (right - left + 1 < bestLength) {
        bestStart = left;
        bestLength = right - left + 1;
      }

      const leftChar = s[left];
      need.set(leftChar, (need.get(leftChar) ?? 0) + 1);
      if ((need.get(leftChar) ?? 0) > 0) {
        missing += 1;
      }
      left += 1;
    }
  }

  return Number.isFinite(bestLength)
    ? s.slice(bestStart, bestStart + bestLength)
    : "";
}