力扣经典题目解析--最小覆盖子串

原题地址: . - 力扣（LeetCode）

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

注意：

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

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

暴力法

暴力法就是遍历所有子串，然后统计子串中每个字符出现的次数，然后跟t中每个字符出现的次数做比较，如果包含t中所有字符并且字符出现的次数大于等于t,则说明该子串符合条件，找出所有满足条件的子串，通过比较得到最小子串

public String minWindow(String s, String t) {
    // 保存自小子串
    String result = "";
    // 统计t中字符串数量
    Map tCharStatis = statis(t);
    // 遍历s
    for (int i = 0; i < s.length(); i++) {
        // 遍历子串,子串范围为[i,j)
        for (int j = i + t.length(); j <= s.length(); j++) {
            String subStr = s.substring(i, j);
            Map subCharStatis = statis(subStr);
            // 如果子串包含t,则判断是否为最小子串
            if (check(subCharStatis, tCharStatis)) {
                if ("".equals(result) || subStr.length() < result.length()) {
                    result = subStr;
                }
            }
        }
    }
    return result;
}
 
// 统计字符串中单个字符数量
private Map statis(String str) {
    Map map = new HashMap<>();
    for (int i = 0; i < str.length(); i++) {
        int count = map.getOrDefault(str.charAt(i), 0);
        count++;
        map.put(str.charAt(i), count);
    }
    return map;
}
 
// 判断子串是否包含t
private boolean check(Map subStatis, Map tStatis) {
    for (Character c : tStatis.keySet()) {
        int subCount = subStatis.getOrDefault(c, 0);
        if (subCount < tStatis.get(c)) return false;
    }
    return true;
}

效果:

代码没问题，但是时间复杂度太高，没法满足需求 

滑动窗口

暴力法的缺点是显而易见的：时间复杂度过大，超出了运行时间限制。在哪些方面可以优化呢？

仔细观察可以发现，我们在暴力求解的时候，做了很多无用的比对：对于字符串“ADOBECODEBANC”，当找到一个符合条件的子串“ADOBEC”后，我们会继续仍以“A”作为起点扩展这个子串，得到一个符合条件的“ADOBECO”——它肯定符合条件，也肯定比之前的子串长，这其实是完全不必要的。

代码实现上，我们可以定义两个指针：指向子串“起始点”的左指针，和指向子串“结束点”的右指针。它们一个固定、另一个移动，彼此交替向右移动，就好像开了一个大小可变的窗口、在不停向右滑动一样，所以这就是非常经典的滑动窗口解决问题的应用场景。所以有时候，滑动窗口也可以归类到双指针法。

public String minWindow1(String s, String t) {
    // 保存自小子串
    String result = "";
    // 统计t中字符串数量
    Map tCharStatis = statis(t);
    int lp = 0;
    int rp = t.length();
    while (rp <= s.length()) {
        String subStr = s.substring(lp, rp);
        Map subCharStatis = statis(subStr);
        // 子串符合条件，则左指针右移
        if (check(subCharStatis, tCharStatis)) {
            if ("".equals(result) || subStr.length() < result.length()) {
                result = subStr;
            }
            lp++;
        } else {
            //不符合条件则右指针右移继续寻找
            rp++;
        }
    }
    return result;
}
 
// 统计字符串中单个字符数量
private Map statis(String str) {
    Map map = new HashMap<>();
    for (int i = 0; i < str.length(); i++) {
        int count = map.getOrDefault(str.charAt(i), 0);
        count++;
        map.put(str.charAt(i), count);
    }
    return map;
}
 
// 判断子串是否包含t
private boolean check(Map subStatis, Map tStatis) {
    for (Character c : tStatis.keySet()) {
        int subCount = subStatis.getOrDefault(c, 0);
        if (subCount < tStatis.get(c)) return false;
    }
    return true;
}

效果:

比之前有进步，但是还需进一步优化 

滑动窗口优化

我们判断S是否满足包含T中所有字符的时候，调用的方法check其实又是一个暴力法：遍历T中所有字符频次，一一比对。上面的复杂度分析也可以看出，遍历s只用了线性时间，但每次都要遍历一遍T的频次哈希表，这就耗费了大量时间。

我们已经知道，每次指针的移动，只涉及到一个字符的增减。所以我们其实不需要知道完整的频次HashMap，只要获取改变的这个字符的频次，然后再和T中的频次比较，就可以知道新子串是否符合要求了。

public String minWindow(String s, String t) {
    // 保存最小子串
    String result = "";
    // 统计t中字符串数量
    Map tCharStatis = statis(t);
    Map subCharStatis = new HashMap<>();
    int lp = 0;
    int rp = 1;
    while (rp <= s.length()) {
        char newChar = s.charAt(rp - 1);
        // t中包含该字符再统计
        if (tCharStatis.containsKey(newChar)) {
            int count = subCharStatis.getOrDefault(newChar, 0);
            subCharStatis.put(newChar, count + 1);
        }
        // 子串符合条件，则左指针右移
        while (check(subCharStatis, tCharStatis) && lp < rp) {
            if ("".equals(result) || rp - lp < result.length()) {
                result = s.substring(lp, rp);
            }
            char removedChar = s.charAt(lp);
            if (tCharStatis.containsKey(removedChar)) {
                subCharStatis.put(removedChar, subCharStatis.getOrDefault(removedChar, 0) - 1);
            }
            lp++;
        }
        rp++;
    }
    return result;
}
 
// 统计字符串中单个字符数量
private Map statis(String str) {
    Map map = new HashMap<>();
    for (int i = 0; i < str.length(); i++) {
        int count = map.getOrDefault(str.charAt(i), 0);
        count++;
        map.put(str.charAt(i), count);
    }
    return map;
}
 
// 判断子串是否包含t
private boolean check(Map subStatis, Map tStatis) {
    for (Character c : tStatis.keySet()) {
        int subCount = subStatis.getOrDefault(c, 0);
        if (subCount < tStatis.get(c)) return false;
    }
    return true;
}