算法面试：如何求最小覆盖子串？

题干与适用场景

给定字符串 s 和 t，在 s 中找出一个最短连续子串，使它包含 t 的每个字符，并达到 t 中对应的 出现次数。字符匹配区分大小写。例如：

s = "ADOBECODEBANC"
t = "ABC"
输出 = "BANC"

t = "AABC" 时，候选窗口必须至少有两个 A、一个 B 和一个 C。只检查字符集合会漏掉重复次数， 这是本题最常见的语义错误。

约束为 1 <= s.length, t.length <= 100000，字符只含大小写英文字母；若答案存在，最短答案唯一。若没有 任何窗口覆盖 t，返回空字符串。本文的实现也防御性处理空 t 和 s 比 t 短的输入，但这两项不属于 标准约束。

近期公开的软件工程师面试记录中，最小覆盖子串仍以原题或“t 中没有重复字符”的变体出现。中文、英文 在线编程题库也都保留了这道题。核心能力是把全局最短区间转化为可维护的局部状态，因此归入 coding； 示例语言不会改变分类。

面试官考察点

第一层是题意建模。强回答会把“包含 t”写成频次约束：对 t 中每个字符 c，当前窗口频次 window[c] >= need[c]。只说“窗口中出现过这些字符”无法处理 t = "AA"。

第二层是从二次枚举找到单调性。右边界右移只会增加字符，合法窗口继续合法；固定右边界后，左边界右移会 逐步删除字符。窗口一旦合法，就可以持续收缩到刚好失效，并在收缩过程中记录最短答案。

第三层是状态压缩。每轮扫描整个频次表会让复杂度退化。实现用 formed 表示“已有多少种目标字符达到需求 频次”，并令 required = need.size。某个字符的窗口频次第一次等于需求时，formed 加一；从等于需求降到 少于需求时，formed 减一。超过需求的额外字符不会重复计数。

最后是正确性与边界。候选人应解释为什么每个右边界对应的最短合法窗口都被检查、为什么丢弃的左端点不会 成为未来更优答案，并准确给出两个指针各自最多移动 s.length 次的线性复杂度。

回答前需要澄清的问题

• 字符是否区分大小写？ 本题区分；若业务要求忽略大小写，应先定义规范化规则，规范化可能改变返回原串

的下标映射。

• “包含”是否要求顺序一致？ 本题只要求频次覆盖，字符在窗口内的顺序不受限制；若要求按顺序出现，问题

会变成最小窗口子序列，当前滑动窗口条件不再成立。

• 重复字符是否按次数计算？ 是。t = "AABC" 需要两个 A，这是选择频次表的直接原因。
• 最短答案出现并列时返回哪个？ 标准题保证最短答案唯一。若取消该保证，本文代码因只在更短时更新，会

返回最早出现的最短窗口。

• 输入字符集是什么？ 约束限定大小写英文字母，所以按 JavaScript UTF-16 代码单元索引不会拆开输入字符。

若扩展到任意 Unicode，需先明确按代码点还是用户可见字素簇匹配。

• 是否允许空字符串？ 标准约束不允许。示范函数将空 t、空 s 或 s.length < t.length 统一返回空串。
• 只返回子串还是还要下标？ 主问题返回子串。若要下标，可以返回 [bestStart, bestStart + bestLength)，

核心算法保持不变。

这些问题直接决定合法性条件、索引方式或返回规则。语言偏好、变量名和哈希表具体实现不会改变算法选择。

30 秒回答框架

“我会用 need 统计目标频次，再用左右指针维护窗口。右指针扩张时，某类字符首次达到需求就让 formed 加一；全部种类满足后，先记录答案，再移动左指针直到窗口失效。这样会检查每个右边界对应的最短合法窗口。 两个指针只向右，每个位置最多进出一次，所以时间是 O(|s| + |t|)，频次表空间是 O(u)。”

分步骤深入解答

第一步：用基础方案明确瓶颈。

固定左端点后，可以不断扩展右端点并维护频次，遇到第一个合法窗口就记录。这避免了为每个子串重新统计， 但最坏仍会从每个左端点重新扫描，时间为 O(|s|^2 + |t|)。若对每个子串重新计数，甚至会达到三次方。

这里的 u 是 t 中不同字符的数量，英文字母约束下最多为 52。线性方案的重点仍是状态设计，不能依赖字符集 很小来掩盖错误的合法性判断。

第二步：定义足以常数时间判断合法的状态。

need 保存目标频次，window 只保存目标字符在当前窗口中的频次。required = need.size 是需要满足的字符 种类数；formed 是已经达到需求频次的种类数。窗口合法当且仅当 formed === required。

更新规则必须围绕“跨越需求阈值”：

加入 c 后：window[c] 从 need[c]-1 变成 need[c]，formed += 1
加入 c 后：window[c] 从 need[c] 变成 need[c]+1，formed 不变
删除 c 前：window[c] 等于 need[c]，删除后会不足，formed -= 1
删除 c 前：window[c] 大于 need[c]，删除后仍满足，formed 不变

如果把 formed 当成已匹配字符总数，额外出现的字符容易被多算；如果每次加入目标字符都加一，又没有对超过 需求的部分做限制，t = "AABC" 会很快触发伪合法状态。

第三步：确定扩张、记录、收缩的顺序。

右指针把 s[right] 纳入窗口并更新状态。窗口合法后进入内层循环：先用区间 [left, right] 更新答案，再 准备删除 s[left]。若删除会让某种字符不足，先把 formed 减一；随后减少频次并右移 left。

“先记录，再删除”保证当前合法窗口不会漏掉。“在删除前判断是否正好等于需求”保证阈值变化准确。判断写在 减少频次之后也可以，但条件必须相应改为“已经小于需求”，代码与解释应保持一致。

第四步：实现线性算法。

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 char of t) {
    need.set(char, (need.get(char) ?? 0) + 1);
  }

  const window = new Map<string, number>();
  const required = need.size;
  let formed = 0;
  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 target = need.get(char);

    if (target !== undefined) {
      const nextCount = (window.get(char) ?? 0) + 1;
      window.set(char, nextCount);
      if (nextCount === target) formed += 1;
    }

    while (formed === required) {
      const length = right - left + 1;
      if (length < bestLength) {
        bestStart = left;
        bestLength = length;
      }

      const leftChar = s[left];
      const leftTarget = need.get(leftChar);
      if (leftTarget !== undefined) {
        const currentCount = window.get(leftChar) ?? 0;
        if (currentCount === leftTarget) formed -= 1;
        window.set(leftChar, currentCount - 1);
      }
      left += 1;
    }
  }

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

实现只为目标字符维护 window。非目标字符仍会影响窗口长度和左边界，因此不能从 s 中预先删除；它们无需 进入频次表。

第五步：写出不变量与正确性证明。

在每次外层循环结束时，维护以下事实：

1. window[c] 等于当前区间 [left, right] 内目标字符 c 的实际出现次数。
2. formed 精确等于满足 window[c] >= need[c] 的目标字符种类数。
3. 内层循环结束后，当前窗口已经失效；刚才枚举过的最后一个合法窗口，是该 right 对应的最短合法窗口。
4. left 只向右移动。任何被跳过的更早左端点产生的窗口都更长，未来右边界继续右移时也不会优于已经检查过

的同右边界候选。

初始化时窗口为空，前两条成立。加入右端字符只按实际频次更新状态，阈值规则保持第二条。合法时不断删除左端 字符；每次删除前记录答案，所以所有以当前 right 结尾的合法候选都被检查，直到第一、二条共同说明窗口 失效。对所有右边界归纳，算法检查了每个右边界下最短的合法窗口；全局最短窗口必然是其中之一，因此最终 记录就是答案。

第六步：走查重复字符。

取 s = "AAABBC"、t = "AABC"：

need = {A:2, B:1, C:1}, required = 3
right=0, A:1  formed=0
right=1, A:2  formed=1
right=2, A:3  formed=1    额外 A 不重复计数
right=3, B:1  formed=2
right=4, B:2  formed=2    额外 B 不重复计数
right=5, C:1  formed=3    [0,5] 合法
移除下标 0 的 A 后 A:2，仍合法，记录 [1,5] = "AABBC"
再移除一个 A 会使 A:1，formed 降为 2，停止收缩

这个例子同时检查三处细节：需求频次大于一、超过需求的字符不增加 formed、删除多余字符后窗口仍可继续 收缩。

第七步：分析复杂度。

构建 need 扫描 t 一次。右指针扫描 s 一次，左指针在整个执行中也最多从 0 移到 s.length；内层 while 的累计次数为 O(|s|)。哈希表操作按平均 O(1) 计，总时间 O(|s| + |t|)。两个频次表最多保存 u 个目标字符，额外空间 O(u)；英文字母约束下 u <= 52。

第八步：用 oracle 和性质验证。

固定用例至少覆盖：

("ADOBECODEBANC", "ABC") -> "BANC"   标准混合输入
("AAABBC", "AABC")       -> "AABBC"  重复需求
("a", "a")               -> "a"      最小规模
("a", "A")               -> ""       大小写敏感、无解
("abc", "abcd")          -> ""       s 比 t 短
("abc", "")              -> ""       防御性空目标

再为短随机字符串运行二次枚举 oracle。对优化结果检查三项性质：结果确实是 s 的连续子串；频次覆盖 t； 不存在更短的覆盖子串。差分测试很适合发现 formed 多算、答案长度少一和删除顺序错误。

当 s 很短、只需一次性处理且性能没有约束时，二次枚举更短，也更容易现场写对。题目给到 100000 长度并 明确要求线性时间时，滑动窗口才是应完成的最终方案。

高质量示范回答

“我先确认这里的包含按字符频次计算，顺序不重要，并且区分大小写。暴力方法可以固定每个左端点向右扩展， 最坏要二次时间。这里有单调性：右端加入字符后，合法窗口不会因扩张变得非法；窗口合法时，可以移动左端 寻找同一右端点下最短的合法窗口。

我会用 need 记录 t 的频次，用 window 记录当前窗口内目标字符的频次。再维护 formed，表示已经达到 需求频次的字符种类数。加入字符后，只有频次刚好达到需求才增加 formed；窗口合法时先记录答案，再删除 左端字符。如果删除前该字符频次正好等于需求，删除会使窗口失效，所以减少 formed。

关键不变量是 window 始终对应 [left, right] 的真实频次，formed 始终等于已满足的目标种类数。内层 循环会检查每个右端点对应的所有合法左边界，停止时刚越过该右端点的最短合法窗口。全局最短答案必在这些 候选中。右指针和左指针都只向右走，每个位置最多加入和移出一次，所以时间是 O(|s| + |t|)，空间是 O(u)。我会用 t 含重复字符、无解、单字符、大小写不同和随机短串对照暴力实现来验证。”

常见错误

• 只用集合记录目标字符 → 无法表达 t 中的重复次数 → 使用需求频次表。
• 每加入一个目标字符就增加匹配数 → 超额字符会制造伪合法状态 → **只在频次首次达到需求时增加

formed。**

• 删除字符后无条件减少 formed → 删除多余副本时窗口仍然合法 → 仅在删除前频次正好等于需求时减少。
• 合法后只收缩一次 → 漏掉同一右边界下更短的窗口 → 用 while 收缩到首次失效。
• 先移动左指针再记录答案 → 可能跳过当前最短合法窗口或产生少一错误 → 先计算 [left, right] 的长度。
• 每轮遍历整个 need 判断合法 → 复杂度多出 u 因子 → 增量维护满足种类数。
• 把子串问题写成子序列算法 → 允许跳过区间内部位置，返回结果不再连续 → 窗口始终用连续下标区间表示。
• 提前过滤 s 的非目标字符后直接切片原串 → 过滤后的下标无法直接映射原字符串 → **保留原串指针，频次表

只忽略非目标字符。**

• 声称内层循环导致二次时间 → 忽略左指针全程单调前进 → 按每个位置最多移出一次做累计分析。
• 只验证标准示例 → 重复需求、无解和大小写边界仍可能错误 → 增加固定反例与随机 oracle。

追问及应对

追问一：为什么 formed 统计字符种类，不统计已匹配字符总数？

两种状态都能设计出正确算法，但种类计数让合法条件和阈值变化更清晰。对于 need[A] = 2，只有 window[A] 从 1 变成 2 时，这一类才完成；第三个 A 不改变完成状态。删除时从 2 降到 1 才撤销完成。 若统计字符总数，加入时必须使用 window[c] <= need[c] 才增加，删除时也要对称维护，条件更容易写错。

追问二：如果 t 保证没有重复字符，可以简化什么？

need 的每个值都为 1，window 可以换成当前窗口内目标字符的计数或集合加计数；但仍需处理同一目标字符在 窗口中出现多次，因为删除一个副本未必使窗口失效。保留通用频次实现只增加很小常数，并能直接应对原题。

追问三：如果要求字符按 t 中的顺序出现呢？

这会变成最小窗口子序列。频次覆盖已经不足以判断合法，例如 s = "cba"、t = "abc" 的频次完全覆盖， 顺序却不成立。可用动态规划记录每个前缀匹配的起点，或对每个候选结尾做向前、向后扫描；需要重新分析 复杂度，本文的 formed === required 条件不能沿用。

追问四：如果要返回所有并列的最短窗口呢？

取消唯一性保证后，先照常维护 bestLength。发现更短窗口时清空结果并加入当前区间；发现长度等于 bestLength 时追加当前区间。若同一文本区间可能被不同路径重复发现，还需按 [left, right] 去重；当前 双指针过程对每个区间只访问一次，无需额外集合。

追问五：如果 s 是无法一次装入内存的字符流呢？

需求频次和双指针状态仍可在线更新，但返回原始子串要求保留当前候选区间。可以用队列保存从 left 到最新 位置的字符及全局偏移；窗口很久都无法满足时，缓存可能接近整个已读流。若只返回长度和偏移，存储压力可按 目标字符位置进一步压缩；若必须返回文本，需要明确最大窗口或外部存储策略。

追问六：如何支持任意 Unicode 文本？

先约定匹配单位。按 Unicode 代码点匹配时，可用 Array.from 或代码点迭代器，并同时保存原字符串的代码单元 偏移以便切片。用户可见字符可能由多个代码点组成；若要求按字素簇匹配，需要可靠的分段器。规范化形式也会 影响“相同字符”的定义，必须在建频次表前统一处理，并保留到原文本的映射规则。

追问七：如何证明随机测试的 oracle 自身可信？

oracle 只用于短串，可以枚举所有 [left, right]，为每个区间直接重新统计频次，再按长度和起点选择答案。 它刻意采用与优化算法不同的控制流，虽然复杂度高，但逻辑直白。固定用例先验证 oracle；随机差分再比较答案 长度、连续性和覆盖频次，降低两个实现共享同一错误的概率。