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.

分析:
Minimum Window String 这个题目的实现涉及到很多细节，所以事先起草一个清晰的思路是很重要的。

s = [A]DOBECODEBANC
t = ABC
想象一下，当前的window是A，left指针指向A，right指针也指向A
为了使窗口出现ABC,我们把right指针向后移动，直到window包括ADOBEC
s = [ADOBEC]ODEBANC
这个时候，你已经得到了其中一个window，并把这个window记录下来。
然后把窗口收缩一下，变成
s = A[DOBEC]ODEBANC
这个时候的窗口就不包含t了，所以要把right指针往右边移动
s = A[DOBECODEBA]NC
现在的窗口又包含ABC了，把这个窗口也记录下来
继续这样收缩left指针，扩张right指针，直到所有窗口都被记录下来，我们就能找到最小的窗口了

时间复杂度很明显是O(n)， 因为实质上只是在遍历s这个字符串。

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 "";
    }
    
}