题干与适用场景
给定字符串 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|)。若对每个子串重新计数，甚至会达到三次方。
| 方案 | 时间复杂度 | 额外空间 | 关键代价 | |---|---:|---:|---| | 每个左端点重新向右扩展 | O(|s|^2 + |t|) | O(u) | 相邻搜索重复读取同一字符 | | 每轮扫描全部目标种类判断合法 | O(|s|u + |t|) | O(u) | 合法性检查反复遍历频次表 | | 滑动窗口加满足种类数 | O(|s| + |t|) | O(u) | 需要严格维护跨越阈值的时机 |
这里的 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 中预先删除；它们无需 进入频次表。
第五步：写出不变量与正确性证明。
在每次外层循环结束时，维护以下事实：
window[c]等于当前区间[left, right]内目标字符c的实际出现次数。formed精确等于满足window[c] >= need[c]的目标字符种类数。- 内层循环结束后，当前窗口已经失效；刚才枚举过的最后一个合法窗口，是该
right对应的最短合法窗口。 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；随机差分再比较答案 长度、连续性和覆盖频次，降低两个实现共享同一错误的概率。