Sliding window leetcode 76. minimum covering substring (hard) 76.76. minimumwindow substring (hard)

One . Title Description ：

         Give you a string  s 、 A string  t . return  s  Covered by  t  The smallest string of all characters . If  s  There is no coverage in  t  Substring of all characters , Returns an empty string  "" .

Advanced ： You can design one in  o(n)  The algorithm to solve this problem in time ？

Example 1：

Input ：s = "ADOBECODEBANC", t = "ABC"
Output ："BANC"
Example 2：

Input ：s = "a", t = "a"
Output ："a"
Example 3:

Input : s = "a", t = "aa"
Output : ""
explain : t Two characters in 'a' Shall be included in s In the string of ,
Therefore, there is no qualified substring , Returns an empty string .

Two . Code ：

        @ #if 1 The code in implements the official optimization requirements ：: If s = "XX⋯XAxBxCXXXX", t = "BAC", Then we should s Pretreated to s = “AxBxC”.

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> window_map, t_map;
        for (const auto &c: t) ++t_map[c] ;
        #if 1
        int start = 0, end = s.size() - 1;
        for(;start <= end; ++start){
            if(t_map.find(s[start]) != t_map.end()){
                break;
            }
        }
        for(;start <= end; --end){
            if(t_map.find(s[end]) != t_map.end()){
                break;
            }
        }
        if(end >= start){
            s = s.substr(start, end - start + 1);
        }else{
            return "";
        }
        if(s.size() < t.size()){
            return "";
        }
        #endif
        string res;
        int cnt = 0;
        for (int right = 0, left = 0; right < s.size(); ++right) {
            ++window_map[s[right]] ;
            if (window_map[s[right]] <= t_map[s[right]]) ++cnt ;
            while (window_map[s[left]] > t_map[s[left]]) --window_map[s[left++ ]];
            if (cnt == t.size()) {
                if (res.empty() || right - left + 1 < res.size())
                    res = s.substr(left, right - left + 1);
            }
        }
        return res;
    }
};

3、 ... and . The problem-solving idea of sliding window ：

        @ What is a sliding window ？ This link is very detailed , There are also some application examples , Don't know what a sliding window is, you can see .

        @ Official optimization requirements : If s = "XX⋯XAxBxCXXXX", t = "BAC", Then we should s Pretreated to s = “AxBxC” We need to put t The characters and frequencies appearing in are counted and stored t_map（ Unordered key value pairs , The blogger of this link explained well , I don't know. I can have a look .） in , Then use the head and tail pointer start and end Point to respectively s = "XX⋯XAxBxCXXXX" The head and tail of , Then shrink , until start and end The character pointed to exists in t_map in （ That is to point to t Characters contained in ）, That is to say start Yes s Medium A,end Yes s Medium C; Cut and get s = " “AxBxC”", Pretreatment completed . The corresponding code is #if 1 The content in .

        @ After pretreatment , Create two pointers left and right,right Used to expand the string so that the window contains t All characters in ,left Used to shrink strings to achieve the effect of both inclusion and shortest , The obtained string that meets the condition rs. If rs.size() < res.size()（res Used to store the currently obtained optimal string ）, So update res = rs; Otherwise, abandon the rs, Keep looking for , until right Arrived at the s At the end of res It's the best solution .