学步园

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.

思路：

题目对时间复杂度要求很高。首先要考虑简化T和S的运算。T中只要统计不同字母个数即可，而S中只有相应T的字母及其位置才有意义。所以先把这些内容抽出来放到一个hash中简化计算。然后考虑的是如何在S中寻找满足T的子串。这时可以使用两个指针指向简化后的S（记作S'），一个向前移动（r_iter），一个不动（l_iter）。在r_iter向前移动到l_iter和r_iter之间的内容满足要求时，检查是否比之前找到的子串短。之后再移动l_iter，并相应的移动r_iter直到找到下一个满足要求的子串。略微复杂的是，可能在这一段中，一个字母被用的次数多于T中给出的次数，这时需要将多余的字母个数计数，但是却又不能计算在和T比较的字母长度之中。这样，扫视一次T和S可以看作O(2n)，而两个指针的扫视是O(n)。总共时间是O(3n)。

题解：

class Solution {
public:
    string minWindow(string S, string T) {
        enum { CHR_MAX = 256 };                                                                            
                                                                                                           
        // Empty input
        if (T == "" || S == "")
            return string("");
    
        array<int, CHR_MAX> TUsage; // character count in string T
    
        // setup the T list to hash the characters
        fill(begin(TUsage), end(TUsage), 0);
        for(auto ch : T)    // hash all used characters
            ++TUsage[ch];
    
        const size_t T_CHARS = T.size();
    
        vector<pair<char, size_t>> SUsage; // characters from T in S
        size_t offset = 0;
        for(auto ch : S)
        {
            if (TUsage[ch] != 0) 
                SUsage.push_back(make_pair(ch, offset)); 
            ++offset;
        }
    
        // minimum window range
        size_t min_l = 0, min_r = S.size()+1;
        size_t old_minl = min_r - min_l;
    
        // record the current window character usage
        size_t tchar_used = 0;
        array<int, CHR_MAX> ChUsage;
        fill(begin(ChUsage), end(ChUsage), 0);
    
        // the search window left/right iterator
        vector<pair<char, size_t>>::const_iterator l_iter = SUsage.begin();
        vector<pair<char, size_t>>::const_iterator r_iter = l_iter;
        size_t new_minl;
    
        // scan the SUsage
        while(l_iter < SUsage.end())
        {
            while(r_iter < SUsage.end() && tchar_used < T_CHARS)
            {
                char ch = r_iter->first;
    
                ++ChUsage[ch];
    
                // register the used character
                if (ChUsage[ch] <= TUsage[ch])
                    ++tchar_used;
    
                ++r_iter;
            }
    
            if (tchar_used == T_CHARS)
            {
                // verify if it is the minimum window
                new_minl = (r_iter - 1)->second - l_iter->second + 1;
                if (new_minl < old_minl)
                {
                    min_r = (r_iter - 1)->second;
                    min_l = l_iter->second;
                    old_minl = new_minl;
                }
    
                // now do the next iteration
                --ChUsage[l_iter->first];
                if (ChUsage[l_iter->first] < TUsage[l_iter->first])
                    --tchar_used;
                ++l_iter;
            }
            else
                break;  // cannot find any more windows
        }
    
        if (min_r == S.size() + 1)
            return string("");
        else
            return S.substr(min_l, min_r - min_l + 1);
    }
};