LeetCode 76. 最小覆盖子串

给定两个字符串s和t，长度分别是m和n，返回 s 中的最短窗口 子串，使得该子串包含t中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串""。

测试用例保证答案唯一。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"输出："BANC"解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"输出："a"解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入:s = "a", t = "aa"输出:""解释:t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s和t由英文字母组成

class Solution { bool is_covered(int cnt_s[],int cnt_t[]) { for(int i='a';i<='z';i++) { if(cnt_s[i]<cnt_t[i]) return false; } for(int i='A';i<='Z';i++) { if(cnt_s[i]<cnt_t[i]) return false; } return true; } public: string minWindow(string s, string t) { int cnt_s[128]{}; int cnt_t[128]{}; for(auto c:t) { cnt_t[c]++; } int m=s.size(); int ansLeft=-1,ansRight=m; int left=0; for(int right=0;right<m;right++) { cnt_s[s[right]]++; while(is_covered(cnt_s,cnt_t)) { if(right-left<ansRight-ansLeft) { ansLeft=left; ansRight=right; } cnt_s[s[left]]--; left++; } } return ansLeft<0?"":s.substr(ansLeft,ansRight-ansLeft+1); } };