Classic problems of sliding window algorithm and general code summary

The questions are as follows:

Give you a string s and a string t. Returns the smallest substring in s that covers t all characters. If there is no substring covering t all characters in s, the empty string "" is returned.

be careful:

For repeated characters in T, the number of characters in the substring we are looking for must not be less than the number of characters in t.
If there is such a substring in s, we guarantee that it is the only answer.

The general code template (or idea) for the sliding window problem is as follows (the key memory is better to memorize * * *):

Note that the essence of sliding window is to use the enlargement of left and right pointers to control the decrease and enlargement of sliding window in decibels The specific basic format of sliding window problem is:

int left=0,right=0,start=0;

//Also define the window size min as the current string size + 1 to facilitate the update of the window size. When the window still does not have this value after the final program is executed, it means that there is no window meeting the conditions in this string!

while(right<length){

/ / first, use the right pointer to continuously expand the window, that is, right continuously executes right + +;

/ / update important variables while continuously updating right (used to record whether the left right window meets the requirements)

While (important variable = = specified requirement){

/ / first record the size of the window at this time (which is also the final result). If the window is smaller, update min and start (subscript for the start position of the window)

/ / update the left pointer (left + +) for different situations

/ / if the element pointed to by the left pointer is removed and the window meets the requirements, directly move the left pointer to the left (left + +). If there is any impact, change the current important variable, so as to launch the cycle of modifying the left pointer to execute the cycle of modifying the right pointer until the important variable meets the requirements again. Modify the left pointer again and update min and start;  

      }

  }

//Then use the obtained start and min to traverse the string to get the information of the specified window! And output

}

The code block for this problem is as follows:

class Solution {
public:
    string minWindow(string s, string t) {
        int m=s.length(),n=t.length();
        if(s==""||t==""||m<n) return "";
        //The reason why the size is set to 128 is that the ASIC code size is 128need, which indicates the number of occurrences of the corresponding character in the corresponding string in t, and have[i] is the number of occurrences of the corresponding character in the temporary window
        int need[128]={0},have[128]={0};
        for(int i=0;i<n;i++){
            need[t[i]]++;
        }
        //Left indicates the left pointer, right indicates the right pointer, count indicates the number of characters in the string t that have appeared in the window (note that when the character I in t (e.g. x times in T) appears in s and is found to be x + 1 (greater than x), count will not be updated, that is, the maximum value of count is the number of characters in T), min is the size of the current minimum window, and start is the starting subscript of the current window
        int left=0,right=0,min=s.length()+1,count=0,start=0;
        //Traverse all strings in string s
        while(right<s.length()){
            //If the character pointed to by the current right pointer does not appear in t, directly move right to end this cycle and judge the next character
            if(need[s[right]]==0){
                right++;
                continue;
            }
            //At this time, it indicates that the character pointed by the right pointer has appeared in the string t
            if(have[s[right]]<need[s[right]]){
                //Indicates that if the number of characters c in the window in s is less than the number required in t, count will be made++
                count++;
            }
            //Because the character pointed to by the right pointer has appeared in the string t at this time, no matter whether the count changes, have[c] has to be added by one, indicating the number of characters c in the window of s plus one
            have[s[right]]++;
            //The above is about the operation of moving the window to the right, and the operation of moving the window to the left (that is, when count==n) means that the characters in the window contain all the characters in t
            right++;
            while(count==n){
                //If the current reduced window value is smaller than the original window, update the window size and the actual position of the window
                if(right-left<min){
                    min=right-left;
                    start=left;
                }
                //Define l as the current window
                if(need[s[left]]==0){
                    //It means that the character l is not in the string t at this time, so just move the left pointer to the left and end the cycle
                    left++;
                    continue;
                }
                //Executing this means that the character L is in the string t at this time, but it is necessary to judge whether hava[l] is equal to need[l], because sometimes, although count==t.leng, the character L in s actually appears more times than that in t
                if(have[s[left]]==need[s[left]]){
                    //Only when they are equal in size can the value of count be changed to exit the while loop (mainly used to move the left pointer to the left)
                    count--;
                }
                //Whether or not to exit the while loop to execute the right shift operation (i.e. whether or not the count changes), when the left pointer moves left and have[l] must change
                have[s[left]]--;
                left++;
            }
        }
        //At this time, min is the required minimum window size, and start is the subscript at the beginning of the minimum window
        //Note that if min==s.length()+1, that is, min does not change, and there is no substring containing t in s, you can directly return the empty string
        if(min==s.length()+1) return "";
        //Define ans to store the final results
        string ans;
        for(int i=start;i<start+min;i++){
            ans+=s[i];
        }
        return ans;
    }
};

The specific explanations are as follows:

Firstly, the sizes of strings S and T are m and N respectively, and then determine the special case, that is, when m==0 or n==0 or m < n, there must be no substring of string t in string s or the substring is an empty string, so the empty string can be output directly. When the number of characters in the character string defined by j = right is the number of times that the number of characters in the character string defined by j = right] will not meet the requirements, and for the number of characters in the character string defined by j = left, it means that the number of characters in the character string defined by j = right will not meet the requirements, Then use right < s.length() to traverse the whole string s, and first expand the window (using right + +). If the current character s[right] is not in T, directly move the pointer to the right (right + +) and continue; Access whether the next can still move right. The next execution must be the case where s[right] is in T, but count + + will be enabled only when have[s[right]] < need [s[right]]; The specific explanation can be seen from the definition of count above, and whether count is added with one or not, the final have[s[right]] will be added with one, because it records the number of true characters s[right] in the window. Once count==n, that is, when the current window has met the feasible window, first determine the size of the current window to see whether it is smaller than min. if so, update min and start (the starting position of the current smaller window) to left, The next step is to continuously move the left pointer under the window that has met the price adjustment to make the window smaller to see whether the conditions are still met. If yes, update min and start. First, if need[s[left]]==0, that is, the current left pointer does not point to the character required by the t string, directly update left + + and jump out of the loop. If it is executed below, it indicates that the current s[left] is the character required by the string in T, and two cases should also be considered, 1: If the number of current characters s[left] in the window have[s[left]] is equal to the number required by string t, need[s[left]] needs to update count --; Make it exit from the reduced window, execute the extended window to find a new window that meets the conditions, and in either case, make have[s[left]] --, and make left + +. Note that the order of the two is irreversible! So far, the Min obtained after the outer loop is the size of the minimum window required, and the corresponding start is the starting subscript corresponding to the minimum window. Note that you should first judge whether min==s.length()+1, that is, it has not changed. If so, it means that the substring of T is not found in S and directly output "". If not, continuously intercept min characters from the subscript start as the ANS string, and finally output ans is the answer!

Tags: C++ Algorithm

Posted by subalan on Tue, 17 May 2022 02:00:21 +0300