76. 最小覆盖子串
题目描述
输入字符串 s 和 t，长度分别为 m 和 n。
在 s 中找一段连续子串，要求 t 里的每个字符都在其中出现，且出现次数不少于它在 t 中的次数。
返回满足要求的最短子串。如果找不到，返回空串 ""。题目保证最短子串唯一。
示例 1
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC"
解释："BANC" 含有 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 <= 10^5s和t只含英文字母。
进阶：能否在 O(m + n) 时间内求解？
解题思路
右指针扩展并用 win 统计频次；have 记录频次达到 need 要求的字符种类数。当 have==need_k 时，先更新最短区间 best，再右移 left，直到覆盖失效。最后按 best 保存的半开区间切片返回。
为什么正确
每次进入收缩循环时，have==need_k，窗口覆盖 t 的所有字符及其次数；best 保存已检查合法窗口中最短窗口的 (长度,左端点,右端点后一位)。
复杂度分析
设 D_s、D_t 分别为 s、t 的不同字符数，L 为返回子串长度。时间 O(|s|+|t|)；辅助空间 O(D_s+D_t)，返回切片另占 O(L)，含输出空间 O(D_s+D_t+L)。
易错点
字符计数要包含重复字符，不能只用集合判断覆盖。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from collections import Counter
class Solution:
def minWindow(self, s,t):
need=Counter(t); win={}; have=0; need_k=len(need); left=0; best=(10**9,0,0)
for right,ch in enumerate(s):
win[ch]=win.get(ch,0)+1
if ch in need and win[ch]==need[ch]: have+=1
while have==need_k:
if right-left+1 < best[0]: best=(right-left+1,left,right+1)
c=s[left]; win[c]-=1
if c in need and win[c] < need[c]: have-=1
left+=1
return s[best[1]:best[2]] if best[0]<10**9 else ""class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>(), win = new HashMap<>();
for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
int have = 0, needK = need.size(), left = 0;
int bestLen = 1_000_000_000, bestL = 0, bestR = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
win.merge(ch, 1, Integer::sum);
if (need.containsKey(ch) && win.get(ch).equals(need.get(ch))) have++;
while (have == needK) {
if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestL = left; bestR = right + 1; }
char c = s.charAt(left); win.merge(c, -1, Integer::sum);
if (need.containsKey(c) && win.get(c) < need.get(c)) have--;
left++;
}
}
return bestLen < 1_000_000_000 ? s.substring(bestL, bestR) : "";
}
}class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> need, win;
for (char c : t) need[c]++;
int have = 0, need_k = need.size(), left = 0;
int best_len = 1e9, best_l = 0, best_r = 0;
for (int right = 0; right < s.size(); right++) {
char ch = s[right];
win[ch]++;
if (need.count(ch) && win[ch] == need[ch]) have++;
while (have == need_k) {
if (right - left + 1 < best_len) best_len = right - left + 1, best_l = left, best_r = right + 1;
char c = s[left]; win[c]--;
if (need.count(c) && win[c] < need[c]) have--;
left++;
}
}
return best_len < 1e9 ? s.substr(best_l, best_r - best_l) : "";
}
};func minWindow(s string, t string) string {
need, win := map[byte]int{}, map[byte]int{}
for i := 0; i < len(t); i++ {
need[t[i]]++
}
have, needK, left := 0, len(need), 0
bestLen, bestL, bestR := int(1e9), 0, 0
for right := 0; right < len(s); right++ {
ch := s[right]
win[ch]++
if n, ok := need[ch]; ok && win[ch] == n {
have++
}
for have == needK {
if right-left+1 < bestLen {
bestLen, bestL, bestR = right-left+1, left, right+1
}
c := s[left]
win[c]--
if n, ok := need[c]; ok && win[c] < n {
have--
}
left++
}
}
if bestLen < int(1e9) {
return s[bestL:bestR]
}
return ""
}var minWindow = function(s, t) {
const need = new Map(), win = new Map();
for (const c of t) need.set(c, (need.get(c) || 0) + 1);
let have = 0, needK = need.size, left = 0, best = [1e9, 0, 0];
for (let right = 0; right < s.length; right++) {
const ch = s[right];
win.set(ch, (win.get(ch) || 0) + 1);
if (need.has(ch) && win.get(ch) === need.get(ch)) have++;
while (have === needK) {
if (right - left + 1 < best[0]) best = [right - left + 1, left, right + 1];
const c = s[left]; win.set(c, win.get(c) - 1);
if (need.has(c) && win.get(c) < need.get(c)) have--;
left++;
}
}
return best[0] < 1e9 ? s.slice(best[1], best[2]) : "";
};function minWindow(s: string, t: string): string {
const need = new Map<string, number>(), win = new Map<string, number>();
for (const c of t) need.set(c, (need.get(c) || 0) + 1);
let have = 0, needK = need.size, left = 0, best = [1e9, 0, 0];
for (let right = 0; right < s.length; right++) {
const ch = s[right];
win.set(ch, (win.get(ch) || 0) + 1);
if (need.has(ch) && win.get(ch) === need.get(ch)) have++;
while (have === needK) {
if (right - left + 1 < best[0]) best = [right - left + 1, left, right + 1];
const c = s[left]; win.set(c, win.get(c)! - 1);
if (need.has(c) && win.get(c)! < need.get(c)!) have--;
left++;
}
}
return best[0] < 1e9 ? s.slice(best[1], best[2]) : "";
};