最小窗口子序列如何在字符串 S 中找到包含 T 的最短区间？（LeetCode 727）

简化版

最小窗口子序列要求在 S 中找最短子串，使 T 是这个子串的子序列。常见做法是从左到右匹配完一个 T 后，再从右往左收缩窗口起点，得到一个候选最短窗口，然后继续向后找下一个候选。

详细版

String minWindow(String s, String t) {
    int n = s.length(), m = t.length();
    int bestStart = -1, bestLen = Integer.MAX_VALUE;
    int i = 0;
    while (i < n) {
        int j = 0;
        while (i < n && j < m) {
            if (s.charAt(i) == t.charAt(j)) j++;
            i++;
        }
        if (j < m) break;
        int end = i - 1;
        j = m - 1;
        while (end >= 0 && j >= 0) {
            if (s.charAt(end) == t.charAt(j)) j--;
            end--;
        }
        int start = end + 1;
        if (i - start < bestLen) {
            bestLen = i - start;
            bestStart = start;
        }
        i = start + 1;
    }
    return bestStart == -1 ? "" : s.substring(bestStart, bestStart + bestLen);
}

这不是普通最小覆盖子串，因为 T 的字符顺序必须保留，不能只看计数。

完整版教学

一、它和最小覆盖子串不同

最小覆盖子串只要求字符数量覆盖，顺序无关；最小窗口子序列要求 T 按顺序出现在窗口里。

S = abcdebdde
T = bde
答案 = bcde

bde 必须按 b -> d -> e 的顺序出现，不能只统计 b、d、e 各一个。

易错点：这道题的窗口是否合法取决于顺序匹配，不取决于字符计数是否覆盖。

二、正向匹配找到右边界

先从某个位置开始向右扫描 S，同时用 j 匹配 T。

while (i < n && j < m) {
    if (s.charAt(i) == t.charAt(j)) j++;
    i++;
}

当 j == m，说明已经找到一个包含完整 T 的窗口，右边界是 i - 1。

三、反向收缩找到最靠右起点

正向匹配得到的窗口不一定最短，因为起点可能太靠左。于是从右边界往左倒着匹配 T：

窗口: b c d e
T:        b d e
从 e 开始倒着找 e、d、b

倒着匹配结束后，end + 1 就是这个右边界下能取得的最靠右起点，也就是当前候选的最短窗口。

阶段	目的	结果
正向扫描	找到能覆盖 T 的右边界	一个可行窗口
反向扫描	尽量右移起点	当前右边界下最短窗口
更新答案	比较长度	全局最短候选

四、为什么下一轮从 `start + 1` 开始

当前候选窗口的起点是 start。如果下一轮仍从 start 或更早开始，会重复得到同样或更长的窗口。把 i 设为 start + 1，相当于尝试寻找下一个可能更短的起点。

best candidate: [start ... i-1]
next search starts at start + 1

这一步不是简单的右指针继续走，而是主动推进左侧候选。

五、复杂度如何理解

这种双向扫描写法最坏可能接近 O(nm) 或 O(n^2) 级别，因为每找到一个候选都可能反向扫一段。它的优点是思路清晰、容易在面试中写对。

如果追求更稳的复杂度，可以用动态规划记录匹配到 T[j] 时窗口起点：

dp[j] = 当前扫描位置下，匹配 T[0..j] 的最靠右起点

但 DP 写法状态更新更容易错，面试要看题目约束选择。

六、边界与返回值

如果 T 为空，按不同题目定义可能返回空串；如果 S 扫完仍无法匹配完整 T，返回空串。

S = abc
T = ac -> abc
S = abc
T = ad -> ""

更新答案时长度用 i - start，因为 i 已经是右边界后一位。

七、常见误区与追问

误区：把它当成最小覆盖子串，用字符计数窗口。 子序列要求顺序，计数不足以判断。
误区：正向匹配成功后不反向收缩。 起点可能很早，窗口不是最短。
误区：更新长度时把 i 当成右边界。 正向循环结束后 i 已经越过右边界一位。
追问：为什么反向收缩有效？ 在固定右边界下，倒序匹配能找到最靠右的合法起点。
追问：下一轮为什么从 start+1 开始？ 更早起点不会产生更短候选，必须尝试排除当前起点。
追问：有没有 DP 解法？ 有，维护匹配到每个 T[j] 的最靠右起点，可做到更规则的 O(nm)。

八、加强记忆

最小窗口子序列的节奏是“向右凑齐 T，向左压缩起点”。它不是计数窗口题，顺序是灵魂。写代码时记住：正向结束的 i 是右边界后一位；反向结束的 end+1 是起点；下一轮从 start+1 继续找新候选。

简化版

详细版