11 最小字符子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。
class Solution {
public:string minWindow(string s, string t) {int n = s.size(), m = t.size();vector<int> res(2, INT_MAX);unordered_map<char, int> h;unordered_map<char, int> hs;for(auto e : t) hs[e]++;int cnt = 0;for(int i = 0, j = 0; i < n; i++){h[s[i]]++;if(hs.find(s[i]) != hs.end()){if(h[s[i]] == hs[s[i]]) cnt++; // 统计当前s中可以匹配t的字符个数}while(cnt == hs.size()) // 可以匹配所有字符时，说明我们找到了一个合法子串{// 尝试更新左端点找到一个最短的子串h[s[j]]--;if(hs.find(s[j]) != hs.end()){if(h[s[j]] < hs[s[j]]) // 左端点的字符更新后如果无法满足和t匹配更新答案和种类数{cnt--;if(i - j + 1 < res[0]){res[0] = i - j + 1;res[1] = j;}}}j++;}}if(res[0] == INT_MAX) return ""; // 无法匹配当前的t字符串return s.substr(res[1], res[0]);}
};作者：稳住心态
链接：https://leetcode.cn/problems/minimum-window-substring/solutions/2583869/ling-shen-tao-lun-guo-lai-de-luo-ji-jian-px52/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。