76. 最小覆盖子串

76. 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明：

• 如果 S 中不存这样的子串，则返回空字符串 ""。
• 如果 S 中存在这样的子串，我们保证它是唯一的答案。

class Solution {
    public String minWindow(String s, String t) {
        if(s == null || t == null || s.length() < t.length()) return "";
        HashMap<Character,Integer> need = new HashMap<>();
        for(int i = 0;i < t.length();i++){
            char c = t.charAt(i);
            need.put(c,need.getOrDefault(c,0) + 1);
        }
        int l = 0,r = 0;
        int ans_l = 0,ans_r = -1,ans_len = Integer.MAX_VALUE;
        //遍历
        while(r < s.length()){
            char cr = s.charAt(r);
            if(need.containsKey(cr)){
                need.put(cr,need.get(cr) - 1);
                //假如覆盖了
                while(match(need)){
                    //记录长度
                    int curLen = r - l + 1;
                    if(curLen < ans_len){
                        ans_len = curLen;
                        ans_l = l;
                        ans_r = r;
                    }
                    //更新左指针
                    char cl = s.charAt(l);
                    if(need.containsKey(cl)){
                        need.put(cl,need.get(cl) + 1);
                    }                   
                    l++;
                }               
            }
            r++;
        }
        return s.substring(ans_l,ans_r + 1);
    }
    private boolean match(Map<Character,Integer> map){
        for(int num : map.values()){
            if(num > 0) return false;
        }
        return true;
    }
}