Description
Solution
The time complexity of the naive solution is . We take each position as the start left boundary, do the line search to find the right boundary between which the sub string contains all the chars in T and record the minimum window.
A better solution is that we keep a left pointer left and right pointer right, both initialized to 0. minWindow is initialzed to MAX_INT.
- First, we increase the
rightpointer untilS[left, right-1]contains all the chars inT - Second, check if (right - left) < minWindow
- If so, record
leftandrightand updateminWindow
- If so, record
- Third, we increase the
leftpointer by 1 - Forth, check if
S[left, right-1]fails to contain all the chars inT- If so,
- If
right == S.size(): END - Else go to First Step
- If
- Else, go to Second step
- If so,
Code
Running time on Leetcode OJ: 304 ms
1 string minWindow(string S, string T) {
2 int left = 0, right = 0;
3 unordered_map<char, int> checkTable;
4 unordered_map<char, queue<int> > char2pos;
5
6 for (int i = 0; i < T.size(); ++ i){
7 if (checkTable.find(T[i]) == checkTable.end()){
8 char2pos[T[i]] = queue<int>();
9 checkTable[T[i]] = 0;
10 }
11 checkTable[T[i]] ++;
12 }
13
14 int nSpan = 0;
15 int minWindow = 2100000000;
16 int lBound = 0, rBound = 0;
17 while(right < S.size()){
18 while(right < S.size() && nSpan != T.size()){
19 if (checkTable.find(S[right]) != checkTable.end()){
20 if (char2pos[S[right]].size() < checkTable[S[right]])
21 nSpan ++;
22 char2pos[S[right]].push(right);
23 }
24 right ++;
25 }
26
27 while(nSpan == T.size()){
28 if (right - left < minWindow){
29 minWindow = (right - left);
30 lBound = left;
31 rBound = right;
32 }
33
34 if (checkTable.find(S[left]) != checkTable.end()){
35 char2pos[S[left]].pop();
36 if (char2pos[S[left]].size() < checkTable[S[left]])
37 nSpan --;
38 }
39 left ++;
40 }
41 }
42
43 return S.substr(lBound, rBound - lBound);
44 }