# [leetcode] Minimum Window Substring

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.

```//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;
}
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 "";
}
//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];
if(map.find(c) == map.end()){
p++;
continue;
}
else{//found in map
//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];
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++;
}
}
}