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

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

Solution: hashmap

字符串处理的题目，和Substring with Concatenation of All Words思路类似，建立一个字典，然后维护一个窗口。区别是在这道题目中，因为可以跳过没在字典里面的字符，所以遇到没在字典里面的字符可以继续移动窗口右端，而移动窗口左端的条件是当找到满足条件的串之后，一直移动窗口左端直到有字典里的字符不再在窗口里。

维护一个HashMap，一开始key包含字典中所有字符，value就是该字符的数量，然后遇到字典中字符时就将对应字符的数量减一。

算法的时间复杂度是O(n),其中n是字符串的长度。空间复杂度则是O(字典的大小)，也就是代码中T的长度。

public class Solution {
    public String minWindow(String S, String T) {
        if(S == null || S.length() == 0)
            return "";
        
        //key is character in T, value is the number of this character
        HashMap map = new HashMap();
        for(int i = 0; i < T.length(); i++) {
            if(map.containsKey(T.charAt(i))) {
                map.put(T.charAt(i), map.get(T.charAt(i)) + 1);
            }else {
                map.put(T.charAt(i), 1);
            }
        }
        
        int left = 0;
        int count = 0;
        int minLen = S.length() + 1;
        int minStart = 0;
        for(int right = 0; right < S.length(); right++) {
            //遇到没在字典里面的字符可以继续移动窗口右端
            if(map.containsKey(S.charAt(right))) {
                map.put(S.charAt(right), map.get(S.charAt(right)) - 1);
                
                if(map.get(S.charAt(right)) >= 0) {
                    count++;
                }
                
                //一直移动窗口左端直到有字典里的字符不再在窗口里
                while(count == T.length()) {  //if count < T.length(),说明T里的字符不在窗口里了
                    if(right - left + 1 < minLen) {
                        minLen = right - left + 1;
                        minStart = left;
                    }
                    
                    if(map.containsKey(S.charAt(left))) {
                        map.put(S.charAt(left), map.get(S.charAt(left)) + 1);
                        
                        if(map.get(S.charAt(left)) > 0) {
                            count--;
                        }
                    }
                    left++;
                }
            }
        }
        if(minLen > S.length()) {
            return "";
        }
        
        return S.substring(minStart, minStart + minLen);
    }
}