LeetCode 76. Minimum Window Substring

76. Minimum Window Substring
思路:
构造一个哈希表结构统计我们的需求，也就是字符串t中每个字符的数量，方便起见如果有需求则哈希表的对应值-1。另外存储一下当前解的起始位置START以及最优解的位置。
扫描字符串s，在位置s[i]时如果能够满足需求（即哈希表中没有负值），则从START开始清除无用的字符直至无法满足需求位置。比如需求是A:1, B:2，START开始的字符是DEFBAB，则清除DEF。清除完成后更新START值并跟当前已知的最优解比较，更新最优解。
啰嗦一句，似乎相当一部分substring类型的题目都能用hash table + two pointers的方式解决。

class Solution {
public:
    static string minWindow(string s, string t) {
        int count_map[128] = {0};
        set<char> req_set;
        int start_index = -1, min_start_index = 0;
        int min_end_index = INT_MAX;
        for (const char& c : t)
        {
            count_map[c] --;
            req_set.insert(c);
        }
        for (int i = 0; i < s.size(); ++i)
        {
            const char c = s[i];
            count_map[c] ++;
            bool require_sufficed = true;
            for (const char& c : req_set)
            {
                if (count_map[c] < 0)
                {
                    require_sufficed = false;
                    break;
                }
            }
            if (!require_sufficed) continue;
            // clear left
            for (int j = start_index + 1; j <= i; ++j)
            {
                if (--count_map[s[j]] < 0)
                {
                    start_index = j;
                    break;
                }
                start_index = j;
            }
            if (i - start_index < min_end_index - min_start_index)
            {
                min_start_index = start_index;
                min_end_index = i;
            }
        }
        if (min_end_index == INT_MAX)
            return "";
        else
            return s.substr(min_start_index, min_end_index - min_start_index + 1);
    }
};