题目

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.

分析

使用双指针。首先尾指针往后扫S，直到包含T中所有字符时，收缩头指针，直到不能收缩为止。记录此时的窗口长度和起始位置。然后重复刚才的操作，找到最小的窗口。
有一个比较难的地方是如何判断出现了T中所有的字符。这个可以使用一个expected数组来记录每个字符应该出现的次数，一个appeared数组来记录每个字符在头尾指针之间出现的次数，以及一个变量n_apd记录在头尾指针之间出现的有效字符的数目。当n_apd==T.size()时，可以认为满足了条件。

实现

class Solution {
public:
    string minWindow(string s, string t) {
        const int ASCII_MAX=256;
        int appeared[ASCII_MAX];
        int expected[ASCII_MAX];
        fill(appeared, appeared+ASCII_MAX, 0);
        fill(expected, expected+ASCII_MAX, 0);
        int wnd_min=INT_MAX, ans_start=0, ans_end=0;
        for(int i=0; i<t.size(); i++)
            expected[t[i]]++;
        int wnd_end, wnd_start=0, n_apd=0;
        for(wnd_end=0; wnd_end<s.size(); wnd_end++){
            if(expected[s[wnd_end]]>0){
                appeared[s[wnd_end]]++;
                if(appeared[s[wnd_end]]<=expected[s[wnd_end]])
                    n_apd++;
            }
            if(n_apd==t.size()){
                while(appeared[s[wnd_start]]>expected[s[wnd_start]] || expected[s[wnd_start]]==0){
                    if(expected[s[wnd_start]]>0) appeared[s[wnd_start]]--;
                    wnd_start++;
                }
                if(wnd_min>wnd_end-wnd_start+1){
                    wnd_min = wnd_end - wnd_start + 1;
                    ans_start = wnd_start; 
                    ans_end = wnd_start;
                }
            }
        }
        if(wnd_min==INT_MAX) return "";
        else return s.substr(ans_start, wnd_min);
    }
};

思考

这题一开始在数据结构的选择上卡住了。最后使用了最基本的数组就完成了操作。再一次让我想起了扎克伯格的一句话
Done is better than perfect.