1 /**
 2  * 
 3  */
 4 package solution;
 5 
 6 import java.util.HashMap;
 7 
 8 /**
 9  * @author whh
10  * 
11  *         Given a string S and a string T, find the minimum window in S which
12  *         will contain all the characters in T in complexity O(n).
13  * 
14  *         For example, S = "ADOBECODEBANC", T = "ABC" Minimum window is "BANC".
15  * 
16  *         Note:
17  * 
18  *         If there is no such window in S that covers all characters in T,
19  *         return the emtpy string "". If there are multiple such windows, you
20  *         are guaranteed that there will always be only one unique minimum
21  *         window in S.
22  */
23 public class MinimumWindowSubstring {
24 
25     /**
26      * @param args
27      */
28     public static void main(String[] args) {
29         MinimumWindowSubstring mws = new MinimumWindowSubstring();
30         String S = "aabbDEE", T = "aabbDEE";
31         System.out.println(mws.minWindow(S, T));
32     }
33 
34     /**
35      * @param S
36      * @param T
37      * @return
38      */
39     public String minWindow(String S, String T) {
40 
41         HashMap<Character, Integer> hasFound = new HashMap<Character, Integer>();
42         HashMap<Character, Integer> needToFind = new HashMap<Character, Integer>();
43 
44         for (int i = 0; i < T.length(); i++) {
45             hasFound.put(T.charAt(i), 0);
46 
47             if (needToFind.containsKey(T.charAt(i))) {
48                 needToFind.put(T.charAt(i), needToFind.get(T.charAt(i)) + 1);
49             } else {
50                 needToFind.put(T.charAt(i), 1);
51             }
52         }
53 
54         int begin = 0;
55         int minWindowSize = S.length();
56         String retString = "";
57 
58         int count = 0;
59 
60         for (int end = 0; end < S.length(); end++) {
61             Character end_c = S.charAt(end);
62             if (needToFind.containsKey(end_c)) {
63                 hasFound.put(end_c, hasFound.get(end_c) + 1);
64                 if (hasFound.get(end_c) <= needToFind.get(end_c)) {
65                     count++;
66                 }
67                 if (count == T.length()) {
68                     while ((!needToFind.containsKey(S.charAt(begin)))
69                             || (hasFound.get(S.charAt(begin)) > needToFind
70                                     .get(S.charAt(begin)))) {
71 
72                         if (needToFind.containsKey(S.charAt(begin))) {
73                             hasFound.put(S.charAt(begin),
74                                     hasFound.get(S.charAt(begin)) - 1);
75                         }
76 
77                         begin++;
78                     }
79 
80                     if ((end - begin + 1) <= minWindowSize) {
81                         minWindowSize = end - begin + 1;
82                         retString = S.substring(begin, end + 1);
83                     }
84                 }
85             }
86         }
87 
88         return retString;
89     }
90 
91 }