最小覆盖子串

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring

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

示例：

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

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

移动窗口解法：

class Solution {
    public String minWindow(String s, String t) {
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0;i<t.length();i++){
            Integer c = map.getOrDefault(t.charAt(i), 0);
            map.put(t.charAt(i),c+1);
        }
        int count = map.size();
        char[] chars = s.toCharArray();
        int left = 0;
        String ans = "";
        for (int i=0;i<s.length();i++){
            char c = chars[i];
            Integer cExist = map.get(c);
            if (cExist != null){
                map.put(c,cExist-1);
                if (cExist - 1 == 0){
                    count--;
                }
            }
            //count==0说明窗口覆盖了子串
            if (count == 0){
                if (i - left + 1 < ans.length() || ans.equals(""))
                    ans = s.substring(left,i+1);
                while(count == 0 && left <= i){
                    char tmp = chars[left];
                    Integer tmpCount = map.get(tmp);
                    if (tmpCount != null){
                        if (i - left + 1 < ans.length())
                            ans = s.substring(left,i+1);
                        if (tmpCount + 1 > 0){
                            count++;
                        }
                        map.put(tmp,tmpCount+1);
                    }
                    left++;
                }
            }
        }
        return ans;
    }
}