Leetcode_76_Minimum Window Substring

[lihe]

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).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

题意：已知字符串S和字符串T，求在S中的最小窗口，使得这个窗口包含了T中的所有字符。

算法思路：

1. 设置两字符哈希数组，map_s与map_t，map_s代表当前处理的窗口区间中的字符数量，map_t代表了字符串T的字符数量；
2. 设置两个指针i和begin指向字符串S的第一个字符；
3. i指针向后逐个扫描字符串中的字符，这个过程中循环检查begin指针是否可以向前移动；
   • 如果当前begin指向的字符，T中没有出现，直接向前移动begin；
   • 如果当前begin指向的字符，T中出现了，但是当前区间窗口中该字符的数量足够，直接向前移动begin，并跟新map_s;
4. 指针i没向前扫描一个字符，即检查是否可以跟新最终的结果；

在整个过程中，使用begin和i维护一个窗口，该窗口中的子串满足题目条件，窗口线性向前滑动，整体时间复杂度为O(n)。

class Solution{
private:
    bool is_window_ok(int map_s[], int map_t[], std::vector<int> &vec_t){
        for(int i = 0; i < vec_t.size(); i++){
            if(map_s[vec_t[i]] < map_t[vec_t[i]]){
                return false;
            }
        }
        return true;
    }

public:
    std::string minWindow(std::string s, std::string t){
        const int MAX_ARRAY_LEN = 128;
        int map_t[MAX_ARRAY_LEN] = {0};
        int map_s[MAX_ARRAY_LEN] = {0};
        std::vector<int> vec_t;
        for(int i = 0; i < t.length(); i++){
            map_t[t[i]]++;
        }
        for(int i = 0; i < MAX_ARRAY_LEN; i++){
            if(map_t[i] > 0){
                vec_t.push_back(i);
            }
        }

        int window_begin = 0;
        std::string result;
        for(int i = 0; i < s.length(); i++){
            map_s[s[i]]++;
            while(window_begin < i){
                char begin_ch = s[window_begin];
                if(map_t[begin_ch] == 0){
                    window_begin++;
                }
                else if(map_s[begin_ch] > map_t[begin_ch]){
                    map_s[begin_ch]--;
                    window_begin++;
                }
                else{
                    break;
                }
            }
            if(is_window_ok(map_s, map_t, vec_t)){
                int new_window_len = i - window_begin + 1;
                if(result == "" || result.length() > new_window_len){
                    result = s.substr(window_begin, new_window_len);
                }
            }
        }
        return result;
    }
};