Leetcode 076. 最小覆盖子串 双指针

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

class Solution {
public:

int sample_map[256];
int inputmap[256];

bool check() {

    for (int i = 0; i < 256; i++) {
        if (inputmap[i] < sample_map[i])
            return false;
    }

    return true;
}

string minWindow(string s, string t) {
    for (int i = 0; i < t.size(); i++) {
        int idx = t[i] - char(0);
        sample_map[idx]++;
    }
    int ans = 999999; string ansStr;

    int l = 0; int r = 0;
    inputmap[s[r]] =1;

    while (l < s.size() && r < s.size()) {
        if (check()) {
            int len = r - l + 1;
            if (len < ans) {
                ans = len; ansStr = s.substr(l, len);
            }
            //尝试从左边缩短字符串 看看是否会依旧包含样例字符串
            inputmap[s[l]]--;
            l++;
        }
        else {
            //已经不满足包含字符串了，从右边扩展字符串
            r++;
            inputmap[s[r]]++;
        }

    }


    return ansStr;
}


};