yicong@algo:~/code/04-substring$ cat 0076-minimum-window-substring.cpp
76. 最小覆盖子串
// 思路
答案窗口的两个端点一定都是 t 里的字符——否则把端点内缩一格仍然覆盖 t,窗口还能更短。 所以只需要处理 s 中属于 t 的字符,其它字符直接跳过。 版本一(你的写法)用「字符 -> 位置列表」记录窗口,每次比对都要扫一遍字符表; 版本二用 formed 计数器把「是否覆盖 t」的判断降到 O(1),时间降到 O(|s|)。
// 时间复杂度
版本一:O(|s| · K),K 是 t 里不同字符的种数(≤ 52) 版本二:O(|s| + |t|),right 和 left 各自最多走完 s 一遍
// 空间复杂度
版本一:O(|s|),window 里存的是窗口内每个字符的位置列表 版本二:O(1),只有 128 的定长表
// 易错点
1. covered 要遍历 ts,而不是遍历 window —— window 里可能压根没出现过 t 的某个字符, 只扫 window 会把"缺字符"误判成"覆盖了"。 2. 版本二里 formed 只在"数量刚好追平"的那一次加一,所以判断是 cnt[in] == need[in]。 写成 cnt[in] >= need[in] 会在同一个字符上反复累加,formed 虚高。 3. 出窗时必须"先比后减":先看 cnt[out] == need[out],再把 cnt[out] 减一。 顺序反了,就永远比不到"刚好够"的那一次,formed 会少减。 4. 版本一记录答案后要删最靠前的字符,删完不一定还覆盖,判定要用 while 而不是 if。 5. 只记长度不够,必须同时记起点 start,否则最后没法 substr。
// 面试口述要点
1. 用双指针在 s 上维护一个窗口,让窗口内包含 t 的全部字符(提示 1); 2. right 右移扩张,直到窗口恰好覆盖 t(提示 2); 3. 一旦覆盖,就左移 left 收缩,每收缩一步都记一次长度,直到刚好不再覆盖(提示 3); 4. right 继续右移,重复直到 right 走到 s 末尾(提示 4)。 讲完再补一句:用 formed 计数器替代逐字符比对,把"是否覆盖"从 O(K) 降到 O(1)。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// ================================================================
// 版本一:字符 -> 位置列表(你的写法)
// ts : t 的哈希表,字符 -> 需要几个
// window : 当前窗口的哈希表,字符 -> 它在 s 中出现的位置(位置递增压入)
// covered : 窗口里每种字符的个数是否都已达到 ts 的要求
// leftmost : 窗口最靠前的位置,也就是当前窗口的左端点
// 每读到一个 t 里的字符就压进 window;只要 covered,说明窗口刚好覆盖 t,
// 记下长度,然后删掉"最靠前位置"的那个字符,把窗口往右缩一格,再判定一次。
// ================================================================
string minWindow(string s, string t) {
unordered_map<char, int> ts; // t 的哈希表:字符 -> 需要几个
for (char c : t) ts[c]++;
unordered_map<char, vector<int>> window; // 当前窗口:字符 -> 它出现的位置(递增)
int minlength = INT_MAX; // 最小覆盖子串的长度
int start = 0; // 最小覆盖子串的起点
string ans = "";
// 窗口是否已经覆盖 t 的全部字符和个数
auto covered = [&]() -> bool {
for (auto& p : ts) {
auto it = window.find(p.first);
if (it == window.end() || (int)it->second.size() < p.second) return false;
}
return true;
};
// 窗口最靠前的字符及其位置
auto leftmost = [&]() -> pair<char, int> {
pair<char, int> res = {0, INT_MAX};
for (auto& p : window)
if (!p.second.empty() && p.second.front() < res.second) res = {p.first, p.second.front()};
return res;
};
for (int right = 0; right < (int)s.size(); right++) {
if (!ts.count(s[right])) continue; // 不是 t 里的字符,不进窗口
window[s[right]].push_back(right); // 压入当前位置
while (covered()) { // 一致:记下长度,然后删掉最靠前位置的字符
auto [leftChar, leftPos] = leftmost();
int len = right - leftPos + 1;
if (len < minlength) {
minlength = len;
start = leftPos;
}
window[leftChar].erase(window[leftChar].begin());
}
}
if (minlength == INT_MAX) return ans;
return s.substr(start, minlength);
}
// ================================================================
// 版本二:数组 + formed 计数器,O(|s|),面试写的版本(对应上面 4 条提示)
// need[c] : t 里字符 c 需要几个
// cnt[c] : 当前窗口里字符 c 有几个
// required : t 里有多少种不同字符
// formed : 已经"凑够数量"的字符种数
// formed == required 等价于"窗口覆盖了 t",O(1) 就能判断,不用扫字符表。
// 非 t 字符的 need 是 0,进窗/出窗时被 need[c] > 0 挡住,cnt 不动,
// 所以不需要像版本一那样显式过滤,它们天然对 formed 没有影响。
// 字符统一用 int 变量接住再当下标:题目保证 s 和 t 只含英文字母,
// ASCII 码都落在 0~127,用 int 接一下既不会越界,也不会触发 gcc 的
// -Wchar-subscripts 警告(char 在某些平台是有符号的,编译器会担心下标为负)。
// ================================================================
string minWindow_v2(string s, string t) {
// need[c] = t 里字符 c 需要几个
int need[128] = {0};
for (int i = 0; i < (int)t.size(); i++) {
int c = t[i];
need[c]++;
}
// required = t 里有几种不同的字符
int required = 0;
for (int c = 0; c < 128; c++) {
if (need[c] > 0) {
required++;
}
}
int cnt[128] = {0}; // cnt[c] = 当前窗口里字符 c 有几个
int formed = 0; // 窗口里"数量已经够了"的字符有几种
int left = 0; // 窗口左端点
int start = 0; // 答案的起点
int minlength = INT_MAX; // 答案的长度
for (int right = 0; right < (int)s.size(); right++) {
// ---------- 第 1 步:right 位置的字符进窗 ----------
// 提示 2:right 右移扩张,直到窗口覆盖 t
int in = s[right];
if (need[in] > 0) { // 不是 t 里的字符,不参与统计
cnt[in]++;
if (cnt[in] == need[in]) { // 这个字符的数量刚好够了
formed++;
}
}
// ---------- 第 2 步:窗口已经覆盖 t,就把 left 往右推,尽量缩短 ----------
// 提示 3:边收缩边记长度,直到刚好不再覆盖
while (formed == required) {
int len = right - left + 1;
if (len < minlength) { // 记下更短的答案
minlength = len;
start = left;
}
int out = s[left]; // left 位置的字符出窗
if (need[out] > 0) {
if (cnt[out] == need[out]) { // 它现在刚好够,出去就不够了
formed--;
}
cnt[out]--;
}
left++;
}
// 提示 4:left 收缩到不再覆盖后,right 继续右移,直到 s 末尾
}
// ---------- 第 3 步:一次都没有覆盖成功过 ----------
if (minlength == INT_MAX) {
return "";
}
return s.substr(start, minlength);
}
};
// 本地测试:输入两个字符串 s 和 t;输出最小覆盖子串,不存在则输出 none
// 同时跑两个版本并比对结果,方便验证优化版和原版等价
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s, t;
if (!(cin >> s >> t)) return 0;
string ans1 = Solution().minWindow(s, t);
string ans2 = Solution().minWindow_v2(s, t);
if (ans1 != ans2) {
cout << "MISMATCH: v1=" << (ans1.empty() ? "none" : ans1)
<< " v2=" << (ans2.empty() ? "none" : ans2) << '\n';
return 0;
}
if (ans1.empty()) {
cout << "none\n";
} else {
cout << ans1 << '\n';
}
return 0;
}