76. Minimum Window Substring
- Total Accepted: 65455
- Total Submissions: 297766
- Difficulty: Hard
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 empty string"". If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
to see which companies asked this question
Show Similar Problems
题解：
调试了好久，终于做出来了。
题解懒得打字了，转一发：
和及类似的思路，使用l和r两个指针维护子串，用Hash表记录T字串中出现的字符。S中，每次循环r右移1位，然后判断r右移之后所指向的字符是否在Hash表中出现过：如果出现过，则表示在T中。此时通过计数器cnt判断T中字符是否都出现过，如果是，则记录l和r之间子串长度，并与最短长度比较。然后逐步右移l并在Hash表中删除l指向的字符直到计数器cnt小于T中字符数量。
注意一下，由于T中同一字符的数量可能减到负值，因此需要2重判断：先判断是否出现此字符，在判断此字符出现的具体数量。
时间复杂度：O(l1+l2)（l1和l2分别为字符串S和T的长度）
空间复杂度：O(l2)
注意：
string的子串： string substr(int pos = 0,int n = npos) const;//返回pos开始的n个字符组成的字符串
1 class Solution { 2 public: 3 string minWindow(string s, string t) { 4 string ans = ""; 5 int mi = INT_MAX; 6 int szs = s.size(); 7 int szt = t.size(); 8 int i,j; 9 int count[200];10 int have[200];11 memset(count,0,sizeof(count));12 memset(have,0,sizeof(have));13 for(i = 0;i < szt;i++){14 count[ t[i] - 'A' ]++;15 }16 int now = 0;17 for(i = 0,j = 0;j < szs;j++){18 int tm = s[j] - 'A';19 have[tm]++;20 if(count[tm] == 0){21 continue;22 }23 else{24 if(have[tm] <= count[tm])25 now++;26 }27 if(now >= szt){28 while(i <= j){29 int ltm = s[i] - 'A';30 if(count[ltm] == 0){31 i++;32 have[ltm]--;continue;33 }34 else{35 if(have[ltm] > count[ltm]){36 i++;37 have[ltm]--;38 }39 else{40 break;41 }42 }43 }44 if(j - i + 1 < mi){45 mi = j - i + 1;46 ans = s.substr(i,j - i + 1);47 }48 }49 }50 return ans;51 }52 };