[LeetCode] Minimum Window Substring

 1 #include <string>
 2 #include <hash_map>
 3 #include <iostream>
 4 #include <map>
 5 using namespace std;
 6 using namespace __gnu_cxx;
 7 
 8 class Solution {
 9 public:
10     string minWindow(string S, string T) {
11         int numS = S.length(),numT = T.length();
12         if(numS<1||numT<1)    return "";
13         int WinStart=0,WinLast=0,WinCount =0,retStart,leng=INT_MAX;
14         hash_map<char, int > need;
15         hash_map<char, bool > exist;
16         for(int i =0;i<numT;i++){
17             need[T[i]]++;
18             exist[T[i]] = true;
19         }
20 
21         bool addorminus;
22         char curchar;
23         while(WinStart<=numS-numT){
24             if(WinCount!=numT&&WinLast<numS){
25                 addorminus = true;
26                 curchar = S[WinLast++];
27             }
28             else{
29                 addorminus = false;
30                 curchar = S[WinStart++];
31             }
32             if(!exist[curchar]) continue;
33             if(addorminus){
34                 if(need[curchar]>0)  WinCount++;
35                 need[curchar]--;
36                 if(WinCount==numT&&leng>WinLast - WinStart){
37                     retStart = WinStart;
38                     leng = WinLast - WinStart;
39                 }
40             }
41             else{
42                 if(WinCount==numT&&leng>WinLast - WinStart+1){
43                     retStart = WinStart-1;
44                     leng = WinLast - WinStart+1;
45                 }
46                 need[curchar] ++;
47                 if(need[curchar]>0)  WinCount--;
48             }
49         }
50         if(leng==INT_MAX)
51             return "";
52         return S.substr(retStart,leng);
53     }
54 };
55 
56 int main()
57 {
58     string s = "1A123BAC1";
59     string t = "AABC";
60     Solution sol;
61 
62     string ret = sol.minWindow(s,t);
63     cout<<ret<<endl;
64     return 0;
65 }

 1 class Solution {
 2 public:
 3     string minWindow(string S, string T) {
 4         if (S.empty() || T.empty())
 5         {
 6             return "";
 7         }
 8         int count = T.size();
 9         int require[128] = {0};
10         bool chSet[128] = {false};
11         for (int i = 0; i < count; ++i)
12         {
13             require[T[i]]++;
14             chSet[T[i]] = true;
15         }
16         int i = -1;
17         int j = 0;
18         int minLen = INT_MAX;
19         int minIdx = 0;
20         while (i < (int)S.size() && j < (int)S.size())
21         {
22             if (count)
23             {
24                 i++;
25                 require[S[i]]--;
26                 if (chSet[S[i]] && require[S[i]] >= 0)
27                 {
28                     count--;
29                 }
30             }
31             else
32             {
33                 if (minLen > i - j + 1)
34                 {
35                     minLen = i - j + 1;
36                     minIdx = j;
37                 }
38                 require[S[j]]++;
39                 if (chSet[S[j]] && require[S[j]] > 0)
40                 {
41                     count++;
42                 }
43                 j++;
44             }
45         }
46         if (minLen == INT_MAX)
47         {
48             return "";
49         }
50         return S.substr(minIdx, minLen);
51     }
52 };