Minimum Window Substring

 1 public class Solution {
 2     /**
 3      * @param source: A string
 4      * @param target: A string
 5      * @return: A string denote the minimum window
 6      *          Return "" if there is no such a string
 7      */
 8     public String minWindow(String source, String target) {
 9         if (source == null || target == null || source.length() < target.length())
10             return "";
11 
12         int count = 0;
13         int[] targetCharCounts = new int[256];
14         int[] allAppeared = new int[256];
15         int start = -1;
16         int end = - 1;
17 
18         String minString = "";
19 
20         for (int i = 0; i < target.length(); i++) {
21             targetCharCounts[target.charAt(i)]++;
22         }
23 
24         for (int i = 0; i < source.length(); i++) {
25             if (targetCharCounts[source.charAt(i)] >= 1) { // character we need
26                 if (start == -1) {
27                     start = i;
28                 }
29 
30                 allAppeared[source.charAt(i)]++;
31                 if (targetCharCounts[source.charAt(i)] >= allAppeared[source.charAt(i)]) {
32                     count++;
33                 }
34 
35                 if (count == target.length() && end == -1) {
36                     end = i;
37                     minString = source.substring(start, end + 1);
38                 }
39                 // decrease the window size
40                 while (start < source.length() && (targetCharCounts[source.charAt(start)] == 0
41                         || allAppeared[source.charAt(start)] > targetCharCounts[source.charAt(start)])) {
42                     if (allAppeared[source.charAt(start)] > 0) {
43                         allAppeared[source.charAt(start)]--;
44                     }
45                     start++;
46                 }
47 
48                 if (i - start + 1 < minString.length() && count == target.length()) {
49                     end = i;
50                     minString = source.substring(start, end + 1);
51                 }
52             }
53         }
54         return minString;
55     }
56 }