最小覆盖子串

题目链接：最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

方法：滑动窗口

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.empty() || t.empty() || t.size() > s.size()) {
            return "";
        }

        int need[128] = {0};
        for (char c : t) {
            need[(unsigned char)c]++;
        }

        int needCount = t.size();     // 还需要匹配多少字符
        int left = 0, right = 0;
        int minLen = INT_MAX;         // 当前找到的最短长度
        int start = 0;                // 最优区间的起始位置

        while (right < (int)s.size()) {
            char rc = s[right];
            if (need[(unsigned char)rc] > 0) {
                needCount--;          // 用掉一个需要的字符
            }
            need[(unsigned char)rc]--; // 窗口中多了一个 rc
            right++;

            // 当前窗口已经包含了所有需要的字符，开始尽量缩小左边界
            while (needCount == 0) {
                // 更新最小区间
                if (right - left < minLen) {
                    minLen = right - left;
                    start = left;
                }

                char lc = s[left];
                need[(unsigned char)lc]++; // 移出左边字符
                if (need[(unsigned char)lc] > 0) {
                    // 移出了一个“必须”的字符，窗口不再满足条件
                    needCount++;
                }
                left++;
            }
        }

        // 注意 substr 的第二个参数是长度，不是右边界
        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
};