LeetCode 笔记系列16.2 Minimum Window Substring [从O(N*M)， O(NlogM)到O(N)，人生就是一场不停的战斗]

题目：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 emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

上一个系列我们讲到了O(N*M)的解法，这里主要的矛盾是，当遇到一个合法的window的时候，我们无法找到高效的办法（最好是O(1)）来找到这个window的起点。下面的O(NlogM)的解法在上一个解法的基础上，使用一个SoredMap来存放当前的window。

该map的key是S的index，value对应S中该index的字母。因为是SortedMap，在发现合法的Window后，总是能通过firstKey和lastKey得到window的长度。而且也免除了使用额外的bit_status来检验合法window的需要。

同样的，当一个字母收集超过了T中要求的数目，那么删除charAppearenceRecorder中对应链表的头节点，同时，还需删除SortedMap中该index为key的entry。代码如下：

 1 public String minWindow2(String S, String T){
 2         HashMap<Character, Integer> needToFill = new HashMap<Character, Integer>();
 3         HashMap<Character, LinkedList<Integer>> charAppearenceRecorder = new HashMap<Character, LinkedList<Integer>>();
 4         SortedMap<Integer, Character> winMap = new TreeMap<Integer, Character>();
 5         int minWinStart = -1;
 6         int minWinEnd = S.length();
 7         for(int i = 0; i < T.length(); i++){
 8             if(!needToFill.containsKey(T.charAt(i))){
 9                 needToFill.put(T.charAt(i), 1);
10                 charAppearenceRecorder.put(T.charAt(i), new LinkedList<Integer>());
11             }else {
12                 needToFill.put(T.charAt(i), needToFill.get(T.charAt(i)) + 1);
13             }
14         }
15         
16         for(int i = 0; i < S.length(); i++){
17             char c = S.charAt(i);
18             if(needToFill.containsKey(c)){
19                 LinkedList<Integer> charList = charAppearenceRecorder.get(c);
20                 if(charList.size() < needToFill.get(c)){
21                     charList.add(i);
22                     winMap.put(i, c);
23                 }else {
24                     //如果某个字母收集过了，需要删除该字母出现的最小的index，保留靠右的部分
25                     int idxToErase = charList.removeFirst();
26                     winMap.remove(idxToErase);
27                     winMap.put(i, c);
28                     charList.add(i);
29                 }
30                 if(winMap.size() == T.length()){
31                     int start = winMap.firstKey();
32                     int end = winMap.lastKey();
33                     if(end - start < minWinEnd - minWinStart){
34                         minWinStart = start;
35                         minWinEnd = end;
36                     }
37                 }
38             }
39         }
40         
41         return minWinStart != -1 ? S.substring(minWinStart, minWinEnd + 1) : "";
42     }

O(NlogM)

代码的流程很符合O(N*M)的方法。就不“举一个栗子”了吧。

总结下：

1.合理运用embeded的数据结构。