题目描述
给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字母的最小子串。
样例
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明
- 如果 S 中不存这样的子串,则返回空字符串
""
。 - 如果 S 中存在这样的子串,我们保证它是唯一的答案。
算法
(哈希表+双指针) $O(m + n)$
由于只要求包含T
的所有字母,并不要求出现的顺序也相同,我们可以先开一个哈希表记录T
中每个字符出现的次数。然后我们可以枚举窗口的终点,然后从终点到起点扫描S
串,每次将头指针的字符放入另一个哈希表,当队头字符在两个哈希表中的次数相同时,我们将cnt
加一,当cnt
为哈希表的大小时说明此时窗口包含了全部的字符,更新答案。
可以观察到本题具有单调性:当我们枚举窗口的终点时,对于每个终点(自变量),如果存在以它为终点的包含T
的所有字符的窗口,那么在这些窗口中一定存在一个最近的起点(因变量),而当终点右移的时候,起点也一定往后移动,所以可以用双指针来处理。每次将右边界向后移动,当左边界的字符个数超出需要的个数时,我们移动左边界,因为此时窗口比之前的窗口更优。
同样是用双指针,不过这里移动左边界的逻辑与 LeetCode 3. Longest Substring Without Repeating Characters 稍有不同,它是当右边界字符不满足要求时移动左边界。
注意一些边界条件的处理,对于S
串中T
串不包含的字符我们也可以放入哈希表中,这样可以方便处理。
C++ 代码
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> hash;
for (auto c : t) hash[c] ++ ;
int n = hash.size();
string res;
unordered_map<char, int> h;
for (int i = 0, j = 0, cnt = 0; j < s.size(); j ++ ) {
h[s[j]] ++ ;
if (h[s[j]] == hash[s[j]]) cnt ++ ;
while (i <= j && h[s[i]] > hash[s[i]]) {
h[s[i]] -- ;
i ++ ;
}
if (cnt == n && (res.empty() || j - i + 1 < res.size()))
res = s.substr(i, j - i + 1);
}
return res;
}
};