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. 使用一个map记录t中所有的字符及其个数，使用变量count来记录t的字符个数。
2. 使用begin，end两个pointer来表示window。
3. 向右移动end来扩展window，若该字符在map中的个数大于0，则count减1，并将map中的个数减1。此刻若window某个t中字符出现的次数多于t中的次数，则map中的个数会是负数，但不会影响count。
4. 当count等于0时，说明此时window中已经有了t中的所有字符，此刻可以更新min window的长度及起始处head。
5. 同时begin可以继续左移，去掉不必要的字符，来获得min window。当该字符在map中的个数等于0，则说明不包括它的话，window将不符合要求。每次都将map中该字符的个数加1。
6. 扫描完整个string，即可获得min window。

public class Solution {
    public String minWindow(String s, String t) {
        int[] map = new int[128];
        for(int i = 0; i < t.length(); i++) map[t.charAt(i)]++;
        int count = t.length(), begin = 0, end = 0, head = 0;
        int minLen = Integer.MAX_VALUE;
        while(end < s.length()) {
            if(map[s.charAt(end)]-- > 0) count--;
            end++;
            while(count == 0) {
                if(end - begin < minLen) {
                    minLen = end - begin;
                    head = begin;
                }
                if(map[s.charAt(begin)]++ == 0) count++;
                begin++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(head, head + minLen);
    }
}