Force deduction 76 questions, minimum covering string

Power button 76 topic , Minimum overlay string

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

Be careful ：

• about t Duplicate characters in , The number of characters in the substring we are looking for must not be less than t The number of characters in the .
• If s There is such a substring in , We guarantee that it is the only answer .

I/o sample

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

 Input ：s = "a", t = "a"
 Output ："a"

 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 .

solution ： The sliding window

    string minWindow(string s,string t)
    {
    
        int slength=s.size();
        int tlength=t.size();

        // establish hash To store s,t Value in character 
        unordered_map<char,int>shash,thash;
        // take t The characters of the string are saved to thash in 
        for(char temp:t)
        {
    
            thash[temp]++;
        }

        // Defining variables , Left pointer and right pointer 
        int left=0,right=0;
        // Define the difference between two strings 
        int distance=0;
        // Minimum string length 
        int minLen=slength+1;
        // Subscript of starting position 
        int begin=0;

        // Create a sliding window 

        while (right<slength)
        {
    
            char temp=s[right];
            // If in string t Does not exist in the s Corresponding elements in , Then continue to move the right pointer 
            if(thash.count(temp)==0)
            {
    
                right++;
                continue;
            }
            
            // Add the current character to hash In the table , And move the right pointer 
            
            shash[temp]++;

            //distance  Indicates that the sliding window contains t Number of the same number of characters in , The number of single characters in the window is greater than t The number of characters corresponding to the number of characters in the 
            
            // Judge the difference between characters 
            // If s In the string is equal to the string t String in , Continue to increase 
            if(shash[temp]==thash[temp])
            {
    
                distance++;
            }
            right++;
            // Handle the left pointer , Because strings t It can be repeated 
            while(distance==thash.size())
            {
    
                // Update the length of the minimum string 
                if(right-left<minLen)
                {
    
                    minLen=right-left;
                    begin=left;
                }

                // If the string t non-existent s Corresponding elements in , Continue to move the left pointer 
                char ltemp=s[left];

                if(thash.count(ltemp)==0)
                {
    
                    left++;
                    continue;
                }

                //s The characters of ltemp The number is exactly the same as t The number of is equal , Means that the two just meet , The representative is going to be on the team 
                if(shash[ltemp]==thash[ltemp])
                {
    
                    distance--;
                }
                shash[ltemp]--;
                left++;
            }
        }
        
        // Whether the matching is successful depends on whether the value of the minimum length changes 
        return (minLen==slength+1)?"":s.substr(begin,minLen);
    }