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.lengthn t.length1 m, n 105s和t由英文字母组成class Solution { bool is_covered(int cnt_s[],int cnt_t[]) { for(int ia;iz;i) { if(cnt_s[i]cnt_t[i]) return false; } for(int iA;iZ;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 ms.size(); int ansLeft-1,ansRightm; int left0; for(int right0;rightm;right) { cnt_s[s[right]]; while(is_covered(cnt_s,cnt_t)) { if(right-leftansRight-ansLeft) { ansLeftleft; ansRightright; } cnt_s[s[left]]--; left; } } return ansLeft0?:s.substr(ansLeft,ansRight-ansLeft1); } };