Leetcode (76) -- Minimum Covering substring

Leetcode（76）—— Minimum cover substring

subject

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 .

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 .

Tips ：

• $1$ <= s.length, t.length <= $10^5$
• s and t It's made up of English letters

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

Answer key

Method 1 sliding window ：

Ideas

​​   Sliding window can be used to solve the character matching problem of some columns , Typical problems include ： In string $s$ The shortest substring found in , So that it can cover the target string $t$. For the target string $t$, We can use the string $s$ Slide up the window , When the window contains $t$ After all characters in , We will consider whether we can shrink the window according to the meaning of the question .
​​   In the process of sliding the window , We can violently count whether the characters contained in the window meet the requirements of the topic , But this does not take advantage of the basic properties of sliding windows . in fact , The window sliding process can be divided into the following two basic operations ：

• Slide the right edge of the window one bit to the right ： Add a new character at the right end of the window , But the other characters in the window have not changed ;
• Slide the left edge of the window one bit to the right ： A character slides out at the left end of the window , But the other characters in the window have not changed .

​​   therefore , We can consider in 「 One in, one out 」 Based on these two basic operations .

​​   This question requires us to return the string $s$ Contains the string $t$ The smallest window for all characters of the . Include us $t$ The window of all letters of is 「 feasible 」 window .
​​   We can solve this problem with the idea of sliding window . In sliding window type problems, there will be two pointers , One for the 「 extend 」 Of existing windows $r$ The pointer , And a for 「 shrinkage 」 Window $l$ The pointer . At any moment , There's only one pointer moving , And the other is still . We are $s$ Slide up the window , By moving $r$ The pointer keeps expanding the window . When the window contains $t$ After all the required characters , If you can shrink , We shrink the window until we get the smallest Window .

​​   How to determine whether the current window contains all $t$ What about the required characters ？
​​   We can use a hash table to represent $t$ All the characters in and their existing numbers （ be equal to 0 It means that the demand is just met , Greater than 0 To express a lack of , Less than 0 Indicates exceeding ）, Use a hash table to dynamically maintain all the characters in the window and their number , If this dynamic table contains $t$ All characters in the hash table , And the corresponding number is not less than $t$ The number of characters in the hash table , So the current window is 「 feasible 」 Of .

Be careful ： here $t$ Duplicate characters may appear in , So we need to record the number of characters .

​​   Consider how to optimize ？
​​   If $s=\mathrm{X}\mathrm{X}\cdots \mathrm{X}\mathrm{A}\mathrm{B}\mathrm{C}\mathrm{X}\mathrm{X}\mathrm{X}\mathrm{X}$,$t=\mathrm{A}\mathrm{B}\mathrm{C}$, So clearly $[\mathrm{X}\mathrm{X}\cdots \mathrm{X}\mathrm{A}\mathrm{B}\mathrm{C}]$ Is the first to get 「 feasible 」 Section , After we get this feasible interval , We are in accordance with the 「 shrinkage 」 Window principle updates the left border , Get the minimum interval . We actually did some useless operations , When updating the right boundary 「 extend 」 A lot of useless $\mathrm{X}$, When updating the left boundary 「 shrinkage 」 Throw away these useless $\mathrm{X}$, Did so many useless operations , Just to get a short $\mathrm{A}\mathrm{B}\mathrm{C}$. you 're right , Actually in $s$ in , Some characters we don't care about , We only care about $t$ The characters that appear in , Can we preprocess first $s$, Throw those away $t$ Characters that do not appear in , And then make a sliding window ？ Maybe you'll say , This may lead to $\mathrm{X}\mathrm{X}\mathrm{A}\mathrm{B}\mathrm{X}\mathrm{X}\mathrm{C}$ The situation of , The first two can be thrown away when counting the length $\mathrm{X}$, But don't throw away the middle $\mathrm{X}$, How to solve this problem ？ What is the optimized space-time complexity ？
​​   An optimization method ： Found during traversal $t$ The first of these belongs to $t$ character , And make it a sliding window head. When num=0 when , It shows that a window satisfying the meaning of the question has been found so that the characters in t All characters in . It needs to be updated head To remove extra characters , Because the end character must be the demand character and its number is equal to the total demand , Just update head that will do

Code implementation

My initial version ：

class Solution {
    
public:
    string minWindow(string s, string t) {
    
        if(s.size() < t.size()) return "";
        unordered_map<char, pair<int, int>> hash;  // < character ,< Total demand , Total number of existing sliding windows >>
        for(auto& it: t){
    
            if(hash.count(it) == 0){
    
                hash[it].first = 1;
                hash[it].second = 0;
            }else hash[it].first++;
        }
        //  The head, tail and length of the smallest string , The head and tail of the current substring , Traversal pointer , The number of characters that do not exist in the current window 
        int min_head, min_l, head, ptr, num, size;
        head = ptr = 0;
        num = t.size();
        size = s.size();
        min_l = size + 1;
        while(ptr < size){
    
            if(hash.count(s[ptr]) != 0){
    
                hash[s[ptr]].second++;  //  Update the existing total number of sliding windows for this character 
                if(hash[s[ptr]].second <= hash[s[ptr]].first) num--;
                if(num == 0){
    
                    /*  If a character is encountered, the total number of existing sliding windows  >  Total demand , Ensure that the header characters  hash[s[head]].second == hash[s[head]].first  Update  head . to update  head  when , from  head  Until  s  The total number of existing sliding windows for a character in is equal to the total number of requirements   And take the subscript of the character as the new  head */
                    while(true){
    
                        //  The total number of existing sliding windows for each character in the sliding window must be greater than or equal to its total number of requirements 
                        if(hash.count(s[head]) != 0){
    
                            if(hash[s[head]].second == hash[s[head]].first) break;
                            else hash[s[head]].second--;    //  More than its total demand 
                        }
                        head++;
                    }
                    if(ptr-head+1 < min_l){
    
                        min_l = ptr-head+1;
                        min_head = head;
                    }
                }
            }
            ptr++;
        }
        return min_l > size? "": s.substr(min_head, min_l);
    }
};

My improved version （ Optimize the definition of hash table ）：

class Solution {
    
public:
    string minWindow(string s, string t) {
    
        if(s.size() < t.size()) return "";
        unordered_map<char, int> hash;  // < character ,  The number of characters required by the sliding window (0 Means equal to the total demand , Greater than 0 It means that..., is still missing , Less than 0 Indicates exceeding )> 
        for(auto& it: t){
    
            if(hash.count(it) == 0) hash[it] = 1;
            else hash[it]++;
        }
        //  The head, tail and length of the smallest string , The head and tail of the current substring , Traversal pointer , The number of characters that do not exist in the current window 
        int min_head, min_l, head, ptr, num, size;
        head = ptr = 0;
        num = t.size();
        size = s.size();
        min_l = size + 1;
        while(ptr < size){
    
            if(hash.count(s[ptr]) != 0){
    
                hash[s[ptr]]--;  //  Update the existing total number of sliding windows for this character 
                if(hash[s[ptr]] >= 0) num--;
                if(num == 0){
    
                    /*  If a character is encountered, the total number of existing sliding windows  >  Total demand , Ensure that the header characters  hash[s[head]].second == hash[s[head]].first  Update  head . to update  head  when , from  head  Until  s  The total number of existing sliding windows for a character in is equal to the total number of requirements   And take the subscript of the character as the new  head */
                    while(true){
    
                        //  The total number of existing sliding windows for each character in the sliding window must be greater than or equal to its total number of requirements 
                        if(hash.count(s[head]) != 0){
    
                            if(hash[s[head]] == 0) break;
                            else hash[s[head]]++;    //  More than its total demand 
                        }
                        head++;
                    }
                    if(ptr-head+1 < min_l){
    
                        min_l = ptr-head+1;
                        min_head = head;
                    }
                }
            }
            ptr++;
        }
        return min_l > size? "": s.substr(min_head, min_l);
    }
};

My final improved version （ Optimize inner loop ）：

class Solution {
    
public:
    string minWindow(string s, string t) {
    
        if(s.size() < t.size()) return "";
        unordered_map<char, int> hash;  // < character ,  The number of characters required by the sliding window (0 Means equal to the total demand , Greater than 0 It means that..., is still missing , Less than 0 Indicates exceeding )> 
        for(auto& it: t){
    
            if(hash.count(it) == 0) hash[it] = 1;
            else ++hash[it];
        }
        //  The head, tail and length of the smallest string , The head and tail of the current substring , Traversal pointer , The number of characters that do not exist in the current window 
        int min_head, min_l, head, ptr, num, size;
        head = ptr = 0;
        num = t.size();
        size = s.size();
        min_l = size + 1;
        while(ptr < size){
    
            if(hash.count(s[ptr]) != 0){
    
                //  Update the existing total number of sliding windows for this character  --hash[s[ptr]]
                if(--hash[s[ptr]] >= 0) num--;
                //  When  num=0  when , It shows that a window satisfying the meaning of the question has been found so that the characters in  t  All characters in 
                //  It needs to be updated  head  To remove extra characters , Because the end character must be the demand character and its number is equal to the total demand , Just update  head  that will do 
                while(num == 0){
    
                    if(ptr-head+1 < min_l){
    
                        min_l = ptr-head+1;
                        min_head = head;
                    }
                    //  The total number of existing sliding windows for each character in the sliding window must be greater than or equal to its total number of requirements 
                    //  Judge after subtracting the current character , Whether it also meets the requirement that the total number of its existing in the sliding window is not less than the total number of its needs 
                    if(hash.count(s[head]) != 0 && ++hash[s[head]] > 0) num++;
                    head++;
                }
            }
            ptr++;
        }
        return min_l > size? "": s.substr(min_head, min_l);
    }
};

Leetcode Official explanation ：

class Solution {
    
public:
    string minWindow(string s, string t) {
    
        vector<int> chars(128, 0);
        vector<bool> flag(128, false);
        //  Statistics first T Characters in 
        for(int i = 0; i < t.size(); ++i) {
    
            flag[t[i]] = true;
            ++chars[t[i]];
        }
        //  Move sliding window , Constantly changing Statistics 
        int cnt = 0, l = 0, min_l = 0, min_size = s.size() + 1;
        for (int r = 0; r < s.size(); ++r) {
    
            if (flag[s[r]]) {
    
                if (--chars[s[r]] >= 0) {
    
                ++cnt;
                }
                //  If the current sliding window already contains T All characters in ,
                //  Then try to l Move right , Get the shortest substring without affecting the result 
                while (cnt == t.size()) {
    
                    if (r - l + 1 < min_size) {
    
                        min_l = l;
                        min_size = r - l + 1;
                    }
                    if (flag[s[l]] && ++chars[s[l]] > 0) {
    
                        --cnt;
                    }
                    ++l;
                }
            }
        }
        return min_size > s.size()? "": s.substr(min_l, min_size);
    }
};

Netizen Youxie ：

class Solution {
    
public:
    string minWindow(string s, string t) {
    
        int hash[128] = {
    0};
        for (auto& c : t) {
    
            ++hash[c];
        }
        int count[128] = {
    0};
        int cnt = 0;
        int beg = 0;
        int min_len = INT_MAX;
        int min_beg = 0;
        for (int i = 0; i < s.size(); ++i) {
    
            char c = s[i];
            if (hash[c]) {
    
                ++count[c];
                if (count[c] <= hash[c]) {
    
                    ++cnt;
                }
            }
            if (cnt == t.size()) {
    
                for (; beg < i; ++beg) {
    
                    char nc = s[beg];
                    if (hash[nc]) {
    
                        if (count[nc] > hash[nc]) {
    
                            --count[nc];
                            continue;
                        }
                        break;
                    }
                }
                int len = i - beg + 1;
                if (len < min_len) {
    
                    min_len = len;
                    min_beg = beg;
                }
            }
        }
        return min_len == INT_MAX? "" : s.substr(min_beg, min_len);
    }
};

Complexity analysis

Initial version of code analysis ：
Time complexity ： In the worst case, the left and right pointers are right $s$ Go through each element of the , Pairs in hash table $s$ Insert each element in 、 Delete once , Yes $t$ Insert each element in once . Each time you check whether the row is OK, you will traverse the whole $t$ Hash table for , The size of the hash table is related to the size of the character set , Set the character set size to $C$, Then the asymptotic time complexity is $O(C\cdot |s|+|t|)$.
Spatial complexity ： Here, two hash tables and several temporary variables are used as auxiliary space , Each hash table can not store key value pairs that exceed the size of the character set at most , We set the character set size to $C$, Then the asymptotic space complexity is $O(C)$

Improved version of code analysis ：
Time complexity ：$O(n)$,$n$ Refers to a string $s$ The length of . Although in for Nested in a loop while loop , But because while The loop is responsible for moving $ptr$ The pointer , And $ptr$ It only moves from left to right once , So the total time complexity is still $O(n)$.
Spatial complexity ： Here, a hash table and several temporary variables are used as auxiliary space , Each hash table can not store key value pairs that exceed the size of the character set at most , We set the character set size to $C$, Then the asymptotic space complexity is $O(C)$