LeetCode 0076 - Minimum Window Substring
# Hints
- 双指针扫描 + 哈希
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
Given a string and a string , find the minimum window in which will contain all the characters in in complexity .
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:
If there is no such window in that covers all characters in , return the empty string
""
.If there is such window, you are guaranteed that there will always be only one unique minimum window in .
# 题意
给定两个字符串 和 ,求 的最短子串,包含 中的所有字符(重复字符重复计数),如果不存在则返回空串。题目保证满足条件的子串是唯一的(如果存在的话)。
# 题解
本题和 LeetCode 0003 非常相似,同样是双指针扫描。
我们维护 为当前答案,不断令 递进直到发现当前答案合法,此时再不断令 递进直到发现答案不再合法,在此过程中更新答案,重复直到遍历完成即可。
唯一的区别是,本题需要额外考虑如何判断当前子串是否合法。事实上,我们只需要先对 中的字符进行统计,然后在扫描 时进行另外的统计,将两份统计值进行对比即可判断当前子串的合法性。
简单的实现是为 和 分别维护两个桶 和 。首先预处理出 ,并计算出 中存在多少种不同的字符,记为 。在扫描 时,如果发现当前 和 的统计值相同,则此时子串合法,我们可以开始递进 以收缩答案,并在收缩过程中观测何时两份统计值不再相同。
事实上,我们可以将 和 合并为一个桶 ,将两个桶的加法转化为一个桶的加减法,以达到时间和空间常数的优化,但这并不是必要的。具体细节详见代码实现。
时间复杂度为 。
# AC代码
class Solution {
public:
string minWindow(const string & s, const string & t) {
// 初始化
int cnt_s[256] = {0}, cnt_t[256] = {0};
int n = s.length();
// 计数
int sum = 0;
for (auto ch : t) {
if (cnt_t[ch] == 0) {
sum ++;
}
cnt_t[ch] ++;
}
// 双指针扫描
int res[] = {-1, -1};
int left = 0, right = 0;
int cnt = 0;
while (right < n) {
// 计数
char ch = s[right];
cnt_s[ch] ++;
if (cnt_s[ch] == cnt_t[ch]) {
cnt ++;
}
// 收缩
while (left <= right && cnt == sum) {
// 更新答案
if (res[0] == -1 || (res[1] - res[0]) > (right - left)) {
res[0] = left;
res[1] = right;
}
// 计数
char ch = s[left];
cnt_s[ch] --;
if (cnt_s[ch] < cnt_t[ch]) {
cnt --;
}
// 递进
left ++;
}
// 递进
right ++;
}
// 返回
if (res[0] == -1) {
return "";
} else {
return s.substr(res[0], res[1] - res[0] + 1);
}
}
};
# AC代码(优化)
class Solution {
public:
string minWindow(const string & s, const string & t) {
// 初始化
int cnt[256] = {0};
int n = s.length(), m = t.length();
// 计数
for (auto ch : t) {
cnt[ch] ++;
}
// 双指针扫描
int res[] = {-1, -1};
int left = 0, right = 0;
int sum = m;
while (right < n) {
// 计数
char ch = s[right];
if (cnt[ch] > 0) {
sum --;
}
cnt[ch] --;
// 收缩
while (left <= right && sum == 0) {
// 更新答案
if (res[0] == -1 || (res[1] - res[0]) > (right - left)) {
res[0] = left;
res[1] = right;
}
// 计数
char ch = s[left];
if (cnt[ch] >= 0) {
sum ++;
}
cnt[ch] ++;
// 递进
left ++;
}
// 递进
right ++;
}
// 返回
if (res[0] == -1) {
return "";
} else {
return s.substr(res[0], res[1] - res[0] + 1);
}
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01