Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

双指针，维护一个window。

//two pointers algorithm
//自己写的太复杂了，看了一下例解，很简单。直接不用考虑这么多情况
//它用的是一个255长的数组来当hashtable来用，因为字符串中只有ascii码
//并且更新window的算法也比我这个简单，需要有时间再优化一遍，推倒重写。
class Solution {
public:
    void addToMap(unordered_map<char, int> &map, unordered_map<char, int> &temp_map, char &c, size_t &size){
        //first element in this key
        if(temp_map.find(c) == temp_map.end()){
            temp_map[c] = 1;
        }
        else{
            temp_map[c] += 1;
        }
        if(temp_map[c] == map[c]){
            size++;
        }
    }
    
    void removeFromMap(unordered_map<char, int> &map, unordered_map<char, int> &temp_map, char &c, size_t &size){
        temp_map[c] -= 1;
        if(temp_map[c] == map[c] - 1){
            size--;
        }
    }
    
    string minWindow(string s, string t) {
        unordered_map<char, int> map;
        unordered_map<char, int> temp_map;
        
        if(t.empty() || s.empty()){
            return "";
        }
        
        //initialize map
        for(size_t i = 0; i < t.size(); i++){
            char c = t[i];
            //not find in map
            if(map.find(c) == map.end()){
                map[c] = 1;
            }
            //find in map, add 1
            else{
                map[c] += 1;
            }
        }
        //two pointers
        size_t p = 0, q = 0;
        size_t temp_map_size = 0;
        int startIndex = -1;
        int length = 0;
        //find first character in string s that is contained in string t
        while(p < s.size()){
            char c = s[p];
            //found in string t
            if(map.find(c) != map.end()){
                q = p;
                break;
            }
            else{
                p++;
            }
        }
        //string s do not contain any characters in string t
        if(p == s.size()){
            return "";
        }
        addToMap(map, temp_map, s[p], temp_map_size);
        //finish
        if(temp_map_size == map.size()){
            startIndex = q;
            length = p - q + 1;
            return s.substr(startIndex, length);
        }
        //not finish, move on
        p++;
        while(p < s.size()){
            char c = s[p];
            //not found in map
            if(map.find(c) == map.end()){
                p++;
                continue;
            }
            else{//found in map
                addToMap(map, temp_map, c, temp_map_size);
                //fount a suitable window
                if(temp_map_size == map.size()){
                    //first result
                    if(startIndex == -1){
                        startIndex = q;
                        length = p - q + 1;
                    }
                    //not first result
                    else{
                        if (p - q + 1 < length){
                            startIndex = q;
                            length = p - q + 1;
                        }
                    }
                    //move q pointer
                    
                    while(q < p){
                        char c = s[q];
                        //not found in map, move q again
                        if(map.find(c) == map.end()){
                            q++;
                        }
                        //found in map
                        else{
                            //still a suitable window
                            //bug here
                            if(temp_map_size == map.size()){
                                if(p - q + 1 < length){
                                    startIndex = q;
                                    length = p - q + 1;
                                }
                                q++;
                                removeFromMap(map, temp_map, c, temp_map_size);
                            }
                            //not a suitable window
                            else{
                                break;
                            }
                        }
                    }
                    //now q points to a character in map
                    p++;
                }
                //doesn't find a suitable window yet
                else{
                    p++;
                }
            }
        }
        //not found a suitable window
        if(startIndex == -1){
            return "";
        }
        else{
            return s.substr(startIndex, length);
        }
        
    }
};