76 - Minimum Window Substring

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.

思路：

1. 把s扫一遍，每个character放进map
2. 把t扫一遍，记下每个字母出现的次数
3. two pointers
   start ----------end
   start : every time when we find a satisfied window, we move 'start' to right by 1.
   end : every time when we meet a character which is included in target string, we move 'end' to right by 1.
   when all characters needed are included, we update minLen which tells us the final result.
   See the example diagram:
   

从上面可以看出，hashmap用来快速反馈我们已经扫过的substring中的character的情况。end在前面探索，遇到一个就从map中拿走一个，couter用来记录当前这个substring match了多少个目标字母。start移动是为了缩小window size，扫过一个就放回到map中一个，从而最终锁定最短的满足的substring。

public String minimum(String s, String t){
  //hashmap<character, count>
  Map<Character, Integer> map = new HashMap<>();
  for (int i = 0; i < s.length(); i++){
    map.put(s.charAt(i), 0);
  }
  for (int j = 0; j < t.length(); j++){
    if (map.containsKey(t.charAt(j))){
      map.put(t.charAt(j), map.get(t.charAt(j)) + 1);
    }
  }
  int start = 0, end = 0, minStart = 0, minLen = Integer.MAX_VALUE;
  int counter = t.length();
  while (end < s.length()){
    char c = s.charAt(end);
    if (map.get(c) > 0){
      counter--;
    }
    map.put(c, map.get(c) - 1);
    end++;
    while (counter == 0){
      if (minLen > end - start){
        minLen = end - start;
        minStart = start;
      }
      char e = s.charAt(start);
      map.put(e, map.get(e) + 1);
      if (map.get(e) > 0){
        counter++;
      }
      start++;
    }
  }
  return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}