76. 最小覆盖子串
一句话套路滑窗 + need/window 计数,先扩后缩
题目描述
给定两个字符串 s 和 t,长度分别是 m 和 n,返回 s 中的 最短窗口 子串,使得该子串包含 t 中的每一个字符(包括重复字符)。如果没有这样的子串,返回空字符串 ""。
测试用例保证答案唯一。
示例 1:
输入:s = "ADOBECODEBANC", t = "ABC" 输出:"BANC" 解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2:
输入:s = "a", t = "a" 输出:"a" 解释:整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中, 因此没有符合条件的子字符串,返回空字符串。
提示:
m == s.lengthn == t.length1 <= m, n <= 105s和t由英文字母组成
进阶:你能设计一个在
O(m + n) 时间内解决此问题的算法吗?思路
时间
O(|s| + |t|)空间
O(字符集)思路
变长窗口的标准模板 —— 右扩到「合法」,再左缩到「不合法」,在每次合法的时刻记录答案。
用一个 required 计数器(还差多少个字符),避免每步比较整个计数数组。
技巧
cnt[c] 表示「c 还缺几个」。--cnt[c] >= 0 说明这次拿到的正是还缺的那个(注意是>= 0,不是 > 0:补上最后一个缺口时,自减后恰好是 0)。出窗时用反方向的 > 0。
图解
字符串
cabwefgewcwaefgcf(来自本仓库测试数据,下标从 0 开始)逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0076 {
class Solution {
public:
string minWindow(string s, string t) {
if (t.empty() || s.size() < t.size()) return ""; // 空 t 直接返回,不等 `required` 变负后才「碰巧」正确
int cnt[256] = {}; // 按 unsigned char 全值域开,128 会在高字节上越界
for (char c : t) ++cnt[(unsigned char)c];
int required = (int)t.size(); // 还差多少个(含重复)字符
int bestL = 0, bestLen = INT_MAX, l = 0;
for (int r = 0; r < (int)s.size(); ++r) {
if (--cnt[(unsigned char)s[r]] >= 0) --required; // 这个字符是需要的
while (required == 0) { // 窗口已覆盖 t
if (r - l + 1 < bestLen) {
bestLen = r - l + 1;
bestL = l;
}
if (++cnt[(unsigned char)s[l]] > 0) ++required; // 移出后重新缺了
++l;
}
}
return bestLen == INT_MAX ? "" : s.substr(bestL, bestLen);
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0076::Solution s;
CHECK_EQ(s.minWindow("ADOBECODEBANC", "ABC"), string("BANC"));
CHECK_EQ(s.minWindow("a", "a"), string("a"));
CHECK_EQ(s.minWindow("a", "aa"), string("")); // t 有重复,s 不够
CHECK_EQ(s.minWindow("aa", "aa"), string("aa"));
CHECK_EQ(s.minWindow("cabwefgewcwaefgcf", "cae"), string("cwae"));
CHECK_EQ(s.minWindow("abc", ""), string("")); // 空 t 显式返回空串