Minimum Window Substring

 1 public class Solution {
 2     public String minWindow(String S, String T) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5         if (S == null || T == null || S.length() == 0 || T.length() == 0) {
 6             return "";
 7         }
 8         int[] needToFind = new int[256];
 9         int[] hasFound = new int[256];
10 
11         for (int i = 0; i < T.length(); i++) {
12             needToFind[T.charAt(i)]++;
13         }
14 
15         int minWinLen = Integer.MAX_VALUE;
16         int count = 0, tLen = T.length();
17         int winBeg = 0, winEnd = 0;
18         for (int begin = 0, end = 0; end < S.length(); end++) {
19             if (needToFind[S.charAt(end)] == 0) {
20                 continue;
21             }
22             hasFound[S.charAt(end)]++;
23             if(hasFound[S.charAt(end)] <= needToFind[S.charAt(end)]){
24                 count ++;
25             }
26             
27             if(count == tLen){
28                 while(needToFind[S.charAt(begin)] == 0 ||
29                         hasFound[S.charAt(begin)] > needToFind[S.charAt(begin)]){
30                     if(hasFound[S.charAt(begin)] > needToFind[S.charAt(begin)]){
31                         hasFound[S.charAt(begin)]--;
32                     }
33                     begin ++;
34                 }
35                 
36                 int winLen = end - begin + 1;
37                 if(winLen < minWinLen){
38                     winBeg = begin;
39                     winEnd = end;
40                     minWinLen = winLen;
41                 }
42             }
43         }
44 
45         if (count == T.length()) {
46             return S.substring(winBeg, winEnd + 1);
47         }
48 
49         return "";
50     }
51 }