76. 最小覆盖子串

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

class Solution {
   public String minWindow(String s, String t) {
        if (s.isEmpty() || t.isEmpty()) {
            return "";
        }
        Map<Character, Integer> itemsFound = new HashMap<>();
        Map<Character, Integer> toBeFound = new HashMap<>();
        int count = 0;
        int minLen = Integer.MAX_VALUE;
        int l = -1;
        int r = -1;
        //记录字符串t中各字母出现次数
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (toBeFound.containsKey(c)) {
                toBeFound.put(c, toBeFound.get(c) + 1);
            } else {
                toBeFound.put(c, 1);
            }
        }
        for (int start = 0, end = 0; end < s.length(); end++) {
            char e = s.charAt(end);
            //非目标串中字母，右指针继续右移
            if (!toBeFound.containsKey(e)) {
                continue;
            }
            if (itemsFound.containsKey(e)) {
                itemsFound.put(e, itemsFound.get(e) + 1);
            } else {
                itemsFound.put(e, 1);
            }
            if (itemsFound.get(e) <= toBeFound.get(e)) {
                count++;
            }
            if (count == t.length()) {//相等说明已经包含了t
                char ch = s.charAt(start);
                //两种情况可以移动start指针
                while (!toBeFound.containsKey(ch) || itemsFound.get(ch) > toBeFound.get(ch)) {
                    //第一种情况
                    if (!toBeFound.containsKey(ch)) {
                        start++;
                        ch = s.charAt(start);
                        continue;
                    }
                    //第二种情况
                    if (itemsFound.get(ch) > toBeFound.get(ch)) {
                        itemsFound.put(ch, itemsFound.get(ch) - 1);
                        start++;
                        ch = s.charAt(start);
                        continue;
                    }
                }
                if (end - start < minLen) {
                    minLen = end - start;
                    l = start;
                    r = end;
                }
            }
        }
        return l == -1 ? "" : s.substring(l, r + 1);
    }
}