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.
牛逼的讨论:无法理解的大牛思路
https://leetcode.com/discuss/72701/here-10-line-template-that-can-solve-most-substring-problems
另一个讲解:正常人可以懂的思路
http://www.cnblogs.com/TenosDoIt/p/3461301.html
public class Solution { public String minWindow(String S, String T) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. int lens = S.length(), lent = T.length(); int[] srcCnt = new int[256] ;//T中每个字母的个数 int[] foundCnt = new int[256] ;//当前找到T中每个字母的个数 char[] SS = S.toCharArray(); char[] TT = T.toCharArray(); for(int i = 0; i < lent; i++) srcCnt[TT[i]]++; int hasFound = 0;//已经找到的字母数目 int winStart = -1, winEnd = lens;//窗口的左右边界 //两个指针start和i一起扫描 for(int i = 0, start = 0; i < lens; i++) if(srcCnt[SS[i]] != 0) { foundCnt[SS[i]]++; if(foundCnt[SS[i]] <= srcCnt[SS[i]])hasFound++; if(hasFound == lent) {//找到了一个满足的窗口 while(srcCnt[SS[start]] == 0 || foundCnt[SS[start]] > srcCnt[SS[start]]) //当S[start]不在T中,或者找到的S[start]个数大于T中S[start]个数,缩减窗口 { if(srcCnt[SS[start]] != 0) foundCnt[SS[start]]--; start++; } if(winEnd - winStart > i - start) { winStart = start; winEnd = i; } foundCnt[SS[start]]--; start++; hasFound--; } } return winStart != -1 ? S.substring(winStart, winEnd+1) : ""; } }