76. 最小覆盖子串

滑动窗口（双指针）

出处
写得很好 滑动窗口框架

string s, t;
// 在 s 中寻找 t 的「最小覆盖子串」
int left = 0, right = 0;
string res = s;

while(right < s.size()) {
    window.add(s[right]);
    right++;
    // 如果符合要求，移动 left 缩小窗口
    while (window 符合要求) {
        // 如果这个窗口的子串更短，则更新 res
        res = minLen(res, window);
        window.remove(s[left]);
        left++;
    }
}
return res;

#include <iostream>
#include <string>
using namespace std;

class Solution {
  public:
    string minWindow(string s, string t) {
        int count[256] = {0};
        for (auto c : t)
            ++count[c];
        int len = 0, minLength = s.length();
        string res;
        for (int l = 0, r = 0; r < s.length(); ++r) {
            count[s[r]]--;
            if (count[s[r]] >= 0) //是t里的
                ++len;
            while (len == t.length()) {
                if (r - l + 1 <= minLength) {
                    minLength = r - l + 1;
                    res = s.substr(l, r - l + 1);
                }
                count[s[l]]++;
                if (count[s[l]] > 0) //是t里的
                    --len;
                ++l;
            }
        }
        return res;
    }
};

int main() {
    Solution s;
    string str = "ADOBECODEBANC";
    string t = "ABC";
    string res = s.minWindow(str, t);
    cout << res;

    return 0;
}