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.

思路：

这道题最开始只有大概的想法，但是没有成型的算法，直到在网上搜了一些方案以后才做了出来。需要考虑的问题是：

1、如何判断S的子串是否包含了T的所有字母(应该在O(1)时间内)

2、如何在更新起始坐标。

比较直接的想法是用hash，因为字符的范围是0到255，所以可以用256的数组代替。使用toBeFilled表示每个字符需要填充的数目，hasFilled表示至今已经填充好的数目，一个整数count表示S的子串已经包含了T中的字符的数目。用left和right两个指针，首先遍历right，如果right指向的字符在T中存在，那么hasFilled加一，如果hasFilled小于等于toBeFilled的话，表示当前该字符还未填满，那么count加一。一直到count等于T的长度时表示S的子串已经包含T的所有字符。此时再将left尽量向right靠齐，靠齐的过程更新hasFilled，停止条件是如果hasFilled将要小于toBeFilled，更新此时的子串的起始位置，更新最小窗口的大小。因为left和right都至多遍历S的长度次，所以总复杂度是O(n)。

代码：

 1     string minWindow(string S, string T) {
 2         int ls = S.length(), lt = T.length();
 3         if(ls < lt)
 4             return "";
 5         int toBeFilled[256] = {0}, hasFilled[256] = {0};
 6         int left, right, count = 0;
 7         int begin, end, result = INT_MAX;
 8         for(int i = 0; i < lt; i++){
 9             toBeFilled[T[i]]++;
10         }
11         for(left = 0, right = 0; right < ls; right++){
12             if(toBeFilled[S[right]] == 0)
13                 continue;
14             if(hasFilled[S[right]] < toBeFilled[S[right]])
15                 count++;                
16             hasFilled[S[right]]++;
17             if(count == lt){
18                 while(true){
19                     if(toBeFilled[S[left]] == 0){
20                         left++;
21                         continue;
22                     }
23                     if(hasFilled[S[left]] > toBeFilled[S[left]]){
24                         hasFilled[S[left]]--;
25                         left++;
26                     }
27                     else{
28                         if(result > right - left + 1){
29                             begin = left;
30                             end = right;
31                             result = right - left + 1;
32                         }
33                         break;
34                     }
35                 }
36             }
37         }
38         if(count < lt)
39             return "";
40         return S.substr(begin, result);
41     }