Leetcode hot topic Hot 100 day 32: "minimum coverage substring"

Continue to brush LeetCode Hot topic HOT 100 The subject of , And update my blog solutions. stay csdn In my blog, I will try to explain clearly in words , relevant Java Code, you can go to my Personal blog jinhuaiyu.com View in .
subject ： Minimum cover substring
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 <= 105
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 ？

solution： The sliding window
If we use violence to solve this problem , Each time we discuss the qualified substring with a position character as the initial character , You need to O(n²) Time complexity of . The optimization point is if you find a cover string , Then in the inner loop, the characters on the right side don't need to be traversed （ The initial character is fixed ）, Because the longer length is not what we require . But the time complexity has not changed . Can the minimum covering substring of this fixed initial character continue to the next in the outer loop （ The initial character is shifted one bit to the right ） Continue to use ？ In this case, the inner loop is no longer traversed from the initial character . This is the idea of sliding window in this problem .
Imagine in a string s There is a sliding window on the , At first, the left pointer is at the first character , The right pointer starts traversing from left to right , Until you just get to a certain position , The overwritten characters contain strings t All the characters in . At this point, we get a possible result , We recorded . Next, the right pointer does not move , The left pointer starts to move right , Until it just destroys the previous conditions （ The window no longer contains s All characters ）, In the process of moving the left pointer to the right （ Not including when the best conditions are not tenable ）, You will get some smaller coverage substrings , It can be used to update the results .
The left pointer no longer moves , Start moving the right pointer to the right again , Until it meets the conditions when it reaches a certain position , Then move the left pointer , This process is the same as before . We can find out , First move the right pointer to find the tail of the covering substring , When the left pointer moves, all qualified substrings will be found , In this process, we always maintain the smallest covering substring . Finally, the left and right pointers traverse the string s, Find the minimum covering substring , But there are two cycles in this process （ The outer loop moves the right pointer to find the qualified substring , Move the left pointer in an inner loop to minimize the coverage ）, But the left and right pointers just moved from left to right n position , The time complexity of this process is O(n).
How to be in O(n) Determine whether the window contains t String ？ We can use two hash The table stores the window and the string respectively t The number of corresponding characters in （ Window hash There is no need to store tables t Characters not in , Reduce storage space ）, When comparing, you can use iterators in O(n) Compare the two within the time complexity hash surface .

Finally, The code with detailed comments is placed in my Personal blog http://jinhuaiyu.com/leetcode-minimum-window-substring/