【Leetcode】76. Minimum covering substring

1. 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 “” .
The test case ：
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 .

Be careful ：

1. 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 .
2. If s There is such a substring in , We guarantee that it is the only answer .

2. Their thinking

（1） First use two hash tables ht and hs Record separately t and s Window elements in .cnt Record s How many elements in the array match t, When cnt==t.length, Description window s The array contains t The elements in .
（2）len Used to record the contents of t The shortest substring length of ,ans Record the substring that meets the condition each time .
The execution process is as follows ：
The first contains t Array ：

The second contains t Array ：

Third inclusion t Array ：

3. Code

 // The sliding window + Hashtable 
    public String minWindow2(String s, String t) {
    
        HashMap<Character,Integer> hs = new HashMap<Character,Integer>();
        HashMap<Character,Integer> ht = new HashMap<Character,Integer>();
        for(int i = 0;i < t.length();i ++){
    
            ht.put(t.charAt(i),ht.getOrDefault(t.charAt(i), 0) + 1);
        }
        String ans = "";
        int len = 0x3f3f3f3f, cnt = 0;  // How many elements match 
        for(int i = 0,j = 0;i < s.length();i ++)
        {
    
            hs.put(s.charAt(i), hs.getOrDefault(s.charAt(i), 0) + 1);
            if(ht.containsKey(s.charAt(i)) && hs.get(s.charAt(i)) <= ht.get(s.charAt(i))) cnt ++;
            while(j < i && (!ht.containsKey(s.charAt(j)) || hs.get(s.charAt(j)) > ht.get(s.charAt(j))))
            {
    
                int count = hs.get(s.charAt(j)) - 1;
                hs.put(s.charAt(j), count);
                j ++;
            }
            if(cnt == t.length() && i - j + 1 < len){
    
                len = i - j + 1;
                ans = s.substring(j,i + 1);// Intercept j To i+1( barring i+1)
            }
        }
        return ans;
    }

source ： Power button （LeetCode）
link ：link-76 Minimum cover substring