76. Minimum Window Substring

O(n) 想象成柱状图，每个字母频数是一个柱，先把t中的字母频数加上去，然后r指针遍历s每个字符（扩大窗口），先减小各个字母的频数，然后l指针再二次遍历每个字符（缩小窗口）同时增大各个字母的频数直到恢复为正

class Solution {
public:
    string minWindow(string s, string t) {
        int f[128] = {0};
        for (char c : t) {
            ++f[c];
        }
        int n = s.length(), m = t.length(), ll = -1, rr = n;
        for (int r = 0, l = 0, cnt = 0; r < n; ++r) {
            if (--f[s[r]] >= 0) { // 先扩大窗口右端
                ++cnt;
            }
            while (cnt == m) { // 如果当前窗口里包含T的所有字符
                if (r - l < rr - ll) { // 更新结果
                    ll = l;
                    rr = r;
                }
                if (++f[s[l++]] > 0) { // 缩小窗口左端看能不能找到更小的符合要求的窗口
                    --cnt;
                }
            }
        }
        return ll == -1 ? "" : s.substr(ll, rr + 1 - ll);
    }
};

class Solution {
public:
    string minWindow(string s, string t) {
        int smap[256] = {0}, tmap[256] = {0};
        for (const auto &c : t) {
            ++tmap[c];
        }
        string res;
        int n = s.length(), window = INT_MAX;
        for (int i = 0, j = i; i < n; ++i) {
            while (j < n && !contains(smap, tmap)) {
                ++smap[s[j++]];
            }
            if (contains(smap, tmap) && j - i < window) {
                window = j - i;
                res = s.substr(i, window);
            }
            --smap[s[i]];
        }
        return res;
    }

    bool contains(int smap[], int tmap[]) {
        for (int i = 0; i < 256; ++i) {
            if (smap[i] < tmap[i]) {
                return false;
            }
        }
        return true;
    }
};