最小覆盖子串

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.length() < t.length()) return "";

        vector<int> cnts(255, 0);
        for (char ch : t) cnts[ch]--;

        int len = INT_MAX;
        int start = 0;
        int debt = t.length();
        for (int left = 0, right = 0; right < s.length(); right++) {
            if (cnts[s[right]]++ < 0) {
                debt--;
            }

            if (debt == 0) {
                while (cnts[s[left]] > 0) {
                    cnts[s[left]]--;
                    left++;
                }
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    start = left;
                }
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};