最小覆盖子串

题目描述: 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例：

输入：s = "ADOBECODEBANC", t = "ABC"

输出："BANC"

题解：

普通思路记录所有子串并用 hashmap记录对应的最小值

我们可以使用滑动窗口优化:

当窗口[l..r]不包括子串的全部字符时, 我们将r向右移动,直到它包含子串的全部字符。

此时为了得到最小窗口, 我们应该将l向右移动, 直到得到合适的最小窗口。

关键点在于如何判断当前窗口是否包含子串所有的字符：

我们通常用哈希表来处理这种操作, map1存放t中字符和个数(类似: {a:1, b:2, c:1} ), map2用来维护窗口中出现的字符和次数。

只要map2中包含map1中所有字符且对应字母的个数不小于map1中记录的次数, 那么当前窗口就包含子串中所有字符。

思路其实也不难, 但是本题还是比较考验编码能力的。

附上代码：

public class minCoverSubString {
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(minWindow(s, t));
    }
    public static String minWindow(String s, String t) {
        Map<Character, Integer> map1 = new HashMap<Character, Integer>();
        Map<Character, Integer> map2 = new HashMap<Character, Integer>();
        //1.初始化map1
        for(char c : t.toCharArray()){
            map1.put(c , map1.getOrDefault(c, 0) + 1);
        }
        int l = 0;
        int r = 0;
        int ansL = -1, ansR = -1;
        int minLength = Integer.MAX_VALUE;
        while(r <= s.length()) {
            if(r < s.length() && map1.containsKey(s.charAt(r))) {   //s中有t中有的字符时添加
                map2.put(s.charAt(r), map2.getOrDefault(s.charAt(r), 0) + 1); // map2放 r遍历到的字符
            }
            // 校验 map1和 map2
            while(check(map1, map2) && l < r) {     // 窗口可行
                if(r - l + 1 < minLength) {  // 判断当前窗口长度是否小于记录的最小长度
                    ansL = l;
                    ansR = r + 1;
                    minLength = r - l + 1;
                }
                // l缩减时删除map2中记录的值 (如果没有出现这个值, map2中根本就不会记录,跳过就行)
                if(map1.containsKey(s.charAt(l))) {
                    map2.put(s.charAt(l), map2.getOrDefault(s.charAt(l), 0) - 1);
                }
                l++;
            }
            r++;
        }
        // ansL == -1也就是check未通过(check通过一次, 一定会修改ansL)
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

    public static boolean check(Map ori, Map cnt) {
        Iterator iter = ori.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            Character key = (Character) entry.getKey();
            Integer val = (Integer) entry.getValue();
            if (cnt.getOrDefault(key, 0) < val) {
                return false;
            }
        }
        return true;
    }
}