76. Minimum Window Substring

解题思路：leetcode的经典滑动窗口题目，也是面试高频题。给出了两个字符串S, T，找出在S中包含T的最小子串，顺序随意。

分配两个数组(长度为128，这是ASCII码的长度，因为题目并没有说都是字母)

• 一个保存字符串T的所有字符
• 一个保存字符串S中，当前滑动窗口中的所有字符

在对字符串S进行遍历的时候根据与T中的字符串进行比较做相应的处理：

• 如果当前滑动窗口中包含T中的所有字符
  • 如果当前滑动窗口最小，则更新返回值
  • 将rear指针前移并更新当前滑动窗口中的字符
• 如果当前滑动窗口不包含T中的所有字符，将front指针前移，更新窗口中的字符

时间复杂度：O(m + n) / 空间复杂度：O(1) 算法分配的空间固定

class Solution {
public:
    bool isInclude(vector<int>& coll, vector<int>& dict){
        for(int i = 0; i < coll.size(); ++i){
            if(coll[i] < dict[i]) {
                return false;
            }
        }
        return true;
    }
    
    string minWindow(string s, string t) {
        vector<int> dict(128, 0);
        vector<int> coll(128, 0);
        for(auto ch : t){
            ++dict[ch];
        }
        int front = 0, rear = 0;
        int cur_len = INT_MAX;
        string min_substr;
        while(front <= s.size() && rear <= front){
            if(isInclude(coll, dict)){
                if(front - rear < cur_len){
                    cur_len = front - rear;
                    min_substr = s.substr(rear, front - rear);
                }
                --coll[s[rear]];
                ++rear;
            } else if(front != s.size()){
                ++coll[s[front]];
                ++front;
            } else {
                break;
            }
        }
        return min_substr;
    }
};