76.Minimum Window Substring

76.Minimum Window Substring

问题:给出两个字符串,求第一个字符串中包含第二个字符串的最大子串。

思路:建立两个hash表。第一个hash表存储第二个字符串中各个字符出现的次数。第二个hash表初始化跟第一个hash相同,只不过各个字符的value都等于0。然后遍历第一个字符串,只要当前字符出现在第一个hash表中,就将第二个hash的对应字符的value加1,直到第二个hash表中所有字符的value都大于等于第一个hash表,此时找到了第一个可行解的right。

用双指示left和right表示窗口的左右边界。找到第一个可行解的right之后,此时固定right,移动left,直到“第二个hash表恰好满足所有value大于等于第一个hash表value”,此时的left和right就是第一个可行解,看情况判断是否更新窗口大小。这样一直进行,知道right超出边界。

class Solution {
public:
    string minWindow(string s, string t) {
        int s_len=s.size();
        int t_len=t.size();
        if(s_len == 0 || s_len<t_len) return string("");
        //two hash
        unordered_map<char,int> dict;
        unordered_map<char,int> s_dict;
        for(int i=0;i<t_len;i++){
            if(dict.count(t[i])){
                dict[t[i]]++;
            }else{
                dict[t[i]]=1;
                s_dict[t[i]]=0;
            }
        }
       
        int left=0;
        int right=0;
        int distinct_char_num=0;//当前第二个hash表中已经集齐多少个t的字符
        int min_left=0;
        int min_right=s_len-1;
        bool find_flag=0;//判断是否有解
        while(right<s_len){
            //右边界移动
            while(right<s_len && distinct_char_num!=t_len){
                if(dict.find(s[right])!=dict.end()){
                    s_dict[s[right]]++;
                    if(s_dict[s[right]]<=dict[s[right]]){
                        distinct_char_num++;
                        if(distinct_char_num==t_len){
                            find_flag=1;
                            break;
                        }
                    }
                }
                right++;
            }
            //已经找不到可行解了。
            if(right>=s_len) break;
            //左边界移动
            while(left<=right && distinct_char_num==t_len){
                if(dict.find(s[left])!=dict.end()){
                    s_dict[s[left]]--;
                    if(s_dict[s[left]]<dict[s[left]]){
                        //更新最小窗口
                        if((min_right-min_left)>(right-left)){
                            min_right=right;
                            min_left=left;
                        }
                        distinct_char_num--;
                        left++;
                        break;
                    }  
                }
                left++;
            }
         right++;  
        //---------------
        }
        if(find_flag)
            return s.substr(min_left,min_right+1-min_left);
        else
            return string("");
       
    }
};