LeetCode 727. 最小窗口子序列

2022-01-16 HGNULB 约 9 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 727. 最小窗口子序列

题意分析

给定 s 和 t，要在 s 中找一段连续子串，使 t 是这段子串的子序列，并让这段子串尽可能短；长度相同时取起点最靠左的那个，找不到就返回空串。

约束给了很明确的信号：s 最长两万级，t 最长一百级，两者差了两个数量级。这意味着允许把 t 的长度当成一个可以接受的乘数因子，但绝不允许对 s 做平方级的区间枚举。

边界上有三件事必须先想清楚。第一，t 根本没在 s 中出现时要返回空串，而不是返回某个「最接近」的区间。第二，答案窗口的首字符必然等于 t 的首字符、尾字符必然等于 t 的尾字符，否则还能继续截短。第三，等长答案可能不止一个，取最左意味着更新答案的比较必须是严格小于。

解法：双指针扫描 + 回溯收缩

核心思路

最直接的做法是枚举 s 的每一个左端点和右端点，对每个区间再用一次双指针判断 t 是不是它的子序列，取所有合法区间里最短的。复杂度是 $O(n^2 m)$，n 到两万就完全跑不动。

瓶颈在于枚举出来的区间绝大多数两端都是废料：要么左边多带了几个与匹配无关的字符，要么右边还没匹配完就被切断。既然合法窗口的两端一定分别压在 t 的首尾字符上，盲目枚举端点本身就是浪费。

于是观察到一对可以配合使用的性质。从某个起点 i 出发向右贪心匹配 t，第一次把 t 匹配完的位置 r，是「以 i 为起点时最小的右端点」；反过来固定这个 r，从 r 向左倒着匹配 t，第一次倒着匹配完的位置 l，是「以 r 为右端点时最大的左端点」。两次方向相反的扫描一前一后，就把一个候选窗口从两侧同时夹死了。

由此得到贯穿外层循环的不变量：每轮开始时，所有小于 i 的起点所对应的最优窗口都已被考察过；正向扫描结束后 j - 1 是本轮的右端点；反向收缩结束后 start 是以 j - 1 为右端点时最短合法窗口的左端点。下一轮把起点推进到 start + 1，既不会漏掉更优解，也不会重复考察同一个窗口。

解题步骤

用 i 表示本轮扫描的起点，初值为 0，同时准备 bestLen 与 bestStart 记录全局最优窗口。bestLen 的初值必须严格大于任何可能出现的窗口长度，否则长度恰好等于 n 的唯一答案会被漏掉。

正向扫描：从 i 开始让 j 向右走，指针 k 指向 t 中待匹配的字符，字符相等时 k 前进。这一步的目的是找到从 i 出发最早能把 t 匹配完的位置，而不是任意一个能匹配完的位置。

如果 j 已经走到 s 末尾而 k 仍未走完 t，说明从 i 往后再也凑不齐 t，起点更靠右只会更凑不齐，直接结束整个外层循环。这个提前退出不是优化而是必需，否则后面会拿一个没匹配完的 j 去构造窗口。

反向收缩：把 end 放在 j - 1，把 k 放在 m - 1，让 end 向左走并倒着匹配 t，k 减到 -1 时立即停下。停下时 end 正好压在 t 首字符对应的位置上，它是仍能保持窗口合法的最靠右的左端点，也就是本轮的最短左界。

用 j - start 作为本轮窗口长度更新答案，比较用严格小于，这样等长时会保留先出现的窗口，符合题目取最左的要求。

把起点推进到 start + 1 再进入下一轮。之所以不是 i + 1，是因为区间 [i, start] 里的任何起点最终都只会收缩到同一个窗口或更长的窗口，跳过它们不影响正确性，却能保证起点严格单调右移。

以 s = "abcdebdde"、t = "bde" 走一遍：第一轮 i = 0，正向扫描在下标 1 匹配上 b、下标 3 匹配上 d、下标 4 匹配上 e，退出时 j = 5，本轮右端点是 4；反向收缩从 end = 4 起，下标 4 对上 e、下标 3 对上 d、下标 1 对上 b，k 变成 -1 后停在 end = 1，窗口为 [1, 4]，长度 5 - 1 = 4，记下 bestStart = 1、bestLen = 4，答案暂定「bcde」，起点推进到 2。第二轮 i = 2，正向扫描在下标 5 匹配上 b、下标 6 匹配上 d、下标 8 匹配上 e，退出时 j = 9，右端点是 8；反向收缩从 end = 8 起，下标 8 对上 e、下标 7 对上 d、下标 5 对上 b，停在 end = 5，窗口为 [5, 8]，长度 9 - 5 = 4，不小于 bestLen 所以不更新，起点推进到 6。第三轮 i = 6，从下标 6 一直扫到末尾都没能匹配上 t 的首字符 b，k 停在 0，触发提前退出。最终返回从下标 1 开始、长度为 4 的子串「bcde」。

代码实现

// 然后向左回溯，尽量收缩窗口以得到最短左边界。
class Solution {
    public String minWindow(String s, String t) {
        int n = s.length();
        int m = t.length();
        int bestLen = Integer.MAX_VALUE;
        int bestStart = -1;
        int i = 0;

        while (i < n) {
            int j = i;
            int k = 0;

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

            if (k < m) {
                break;
            }

            int end = j - 1;
            k = m - 1;
            while (end >= i) {
                if (s.charAt(end) == t.charAt(k)) {
                    k--;
                    if (k < 0) {
                        break;
                    }
                }
                end--;
            }

            int start = end;
            int len = j - start;
            if (len < bestLen) {
                bestLen = len;
                bestStart = start;
            }

            i = start + 1;
        }

        if (bestStart == -1) {
            return "";
        }
        return s.substring(bestStart, bestStart + bestLen);
    }
}

// 然后向左回溯，尽量收缩窗口以得到最短左边界。
func minWindow(s string, t string) string {
    n := len(s)
    m := len(t)
    bestLen := n + 1
    bestStart := -1
    i := 0

    for i < n {
        j := i
        k := 0

        for j < n && k < m {
            if s[j] == t[k] {
                k++
            }
            j++
        }

        if k < m {
            break
        }

        end := j - 1
        k = m - 1
        for end >= i {
            if s[end] == t[k] {
                k--
                if k < 0 {
                    break
                }
            }
            end--
        }

        start := end
        length := j - start
        if length < bestLen {
            bestLen = length
            bestStart = start
        }

        i = start + 1
    }

    if bestStart == -1 {
        return ""
    }
    return s[bestStart : bestStart+bestLen]
}

复杂度分析

时间复杂度：$O(n \cdot m)$，其中 n、m 分别是 s 和 t 的长度。起点 i 严格单调右移，外层最多进行 n 轮；每一轮的反向收缩长度就是本轮窗口长度，而窗口长度由完成一次 t 匹配所需的跨度决定，摊还之后与 m 成正比。

空间复杂度：$O(1)$，只用了若干个下标与长度变量，返回的子串不计入额外空间。

关键点总结

求「最短合法区间」时，先固定一端再向内收缩另一端，通常比同时枚举两端便宜一个量级，这个套路可以直接迁移到大量区间与窗口题上。

正向找最早右端点、反向找最右左端点，两次方向相反的贪心匹配互为验证，是本题唯一需要想出来的构造，其余都是实现细节。

起点推进到 start + 1 而不是 i + 1，本质上是「跳过必然不更优的候选」，这一步把外层循环从平方级压回线性级。

面试视角：这题常被拿来和 76. 最小覆盖子串对比，面试官真正想听的是你能说清区别——覆盖子串只要求字符计数够，所以窗口能自由伸缩；子序列要求保持顺序，计数窗口那套判定直接失效。先讲透这一点再写代码，比上来就敲键盘更容易拿分。

面试视角：写完后主动补一句「本题还有一个 $O(n \cdot m)$ 的 DP 解法，dp[i][j] 表示 s 前 i 个字符里匹配完 t 前 j 个字符时窗口能取到的最大起始下标」，能表明你知道不止一条路，通常会引出对其中一条的追问。

易错点总结

错误写法：bestLen 的初值取成 n 而不是 n + 1（Go 版尤其容易写错）：s = "bde"、t = "bde" → 唯一答案的长度恰好等于 n，len < bestLen 不成立，答案从未被记录，最终返回空串。

错误写法：反向收缩时 k 减到 -1 后不立即 break，继续执行 end-- 并在下一轮读 t[k]：s = "bbde"、t = "bde" → k 已经是 -1，下一次比较就去访问 t 的 -1 号位，直接抛出下标越界。

错误写法：正向扫描结束后不检查 k < m 就把 j - 1 当右端点：s = "abc"、t = "d" → 拿一个根本没匹配完的位置去反向收缩，start 停在起点上，返回一个完全不含 t 的子串。

错误写法：省掉反向收缩，直接把 [i, j - 1] 当答案：s = "abcdebdde"、t = "bde" → 第一轮返回 [0, 4] 也就是「abcde」，比最优解多带了一个开头的 a。

错误写法：右端点写成 j 而不是 j - 1，或长度写成 j - start + 1：s = "abcdebdde"、t = "bde" → 每个窗口都多算一个字符，返回「bcdeb」这类比最优解长 1 的结果。

错误写法：Java 里写成 s.substring(bestStart, bestLen)：本题最优解 bestStart = 1、bestLen = 4 → 实际截出的是 [1, 4) 即「bcd」，比正确答案少一个字符。

错误写法：更新答案时用 len <= bestLen：输入中存在两个等长的最短窗口时 → 后出现的窗口会覆盖先出现的，返回的不是题目要求的最左答案。

错误写法：下一轮起点写成 i = i + 1：s 中夹杂大段与 t 无关的字符时 → 答案仍然正确，但每个起点都要重跑一次完整的正向扫描，复杂度退化，长输入会超时。

相似题目

题目	难度	考察点
76. 最小覆盖子串	困难	只要求字符计数覆盖、不要求保序，可用可伸缩滑动窗口
392. 判断子序列	简单	只判断是否为子序列，一次正向双指针即可，无需收缩
792. 匹配子序列的单词数	中等	同一个主串上批量匹配多个模式串，重点是按待匹配字符分桶
115. 不同的子序列	困难	求匹配方案数而非最短窗口，只能上二维计数 DP