題目:

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.

分析:
Minimum Window String 這個(gè)題目的實(shí)現(xiàn)涉及到很多細(xì)節(jié)咆爽，所以事先起草一個(gè)清晰的思路是很重要的耻台。

s = [A]DOBECODEBANC
t = ABC
想象一下，當(dāng)前的window是A妆丘，left指針指向A，right指針也指向A
為了使窗口出現(xiàn)ABC,我們把right指針向后移動，直到window包括ADOBEC
s = [ADOBEC]ODEBANC
這個(gè)時(shí)候疾渴，你已經(jīng)得到了其中一個(gè)window，并把這個(gè)window記錄下來寻拂。
然后把窗口收縮一下程奠，變成
s = A[DOBEC]ODEBANC
這個(gè)時(shí)候的窗口就不包含t了，所以要把right指針往右邊移動
s = A[DOBECODEBA]NC
現(xiàn)在的窗口又包含ABC了祭钉，把這個(gè)窗口也記錄下來
繼續(xù)這樣收縮left指針瞄沙，擴(kuò)張right指針，直到所有窗口都被記錄下來，我們就能找到最小的窗口了

時(shí)間復(fù)雜度很明顯是O(n)距境， 因?yàn)閷?shí)質(zhì)上只是在遍歷s這個(gè)字符串申尼。

class Solution {
    public String minWindow(String s, String t) {
        int s_len = s.length(), t_len = t.length(), left = 0, right = -1;
        int best_left = 0, best_right = s_len - 1, match_count = 0, char_count;
        int[] window_map = new int[256];
        int[] t_map = new int[256];
        boolean found = false;

        for(int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            t_map[c]++;
        }
        
        while(true) {
            // Is current window good ? If yes, left ptr moves, otherwise right ptr should move
            if(match_count == t_len) {
                // Keep track of smallest window
                if(right - left <= best_right - best_left) {
                    best_left = left;
                    best_right = right;
                    found = true;
                }
                // Update match_count
                char c = s.charAt(left);
                char_count = t_map[c];
                if(char_count != 0) {
                    int occurences = window_map[c]--;
                    if(occurences <= char_count) match_count--;
                }
                left++;
            }
            else {
                right++;
                if(right >= s_len)
                    break;
                // Update match_count
                char c = s.charAt(right);
                char_count = t_map[c];
                if(char_count != 0) {
                    int occurences = window_map[c]++;
                    if(occurences < char_count) match_count++;
                }
            }
        }
        if(found)
            return s.substring(best_left, best_right + 1);
        return "";
    }
    
}