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由英文字母组成

bool isOverlap(int sMap[], int tMap[]) { for (int i = 0; i < 256; i++ ) { if (sMap[i] < tMap[i]) { return false; } } return true; } char* minWindow(char* s, char* t) { int sLen = strlen(s); int tLen = strlen(t); int sMap[256] = { 0 }; int tMap[256] = { 0 }; for (int i = 0; i < tLen; i++) { tMap[t[i]]++; } int left = 0; int right = 0; int pos = -1; int minLen = INT_MAX; while (right < sLen) { if (tMap[s[right]] == 0) { // 不在t中 right++; continue; } sMap[s[right]]++; while (isOverlap(sMap, tMap) && left <= right) { if (right - left + 1 < minLen) { minLen = right - left + 1; pos = left; } if (tMap[s[left]] > 0) { // 在t中 sMap[s[left]]--; } left++; } right++; } if (pos == -1) { return ""; } char* rst = (char*)calloc(minLen + 1, sizeof(char)); strncpy(rst, s + pos, minLen); return rst; }