76. 最小覆盖子串

原题链接：

76. 最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring/description/

完成情况：

解题思路：

上述代码是解决LeetCode上编号为76的题目“Minimum Window Substring（最小覆盖子串）”的一个实现。此问题是要找到字符串S中的最小窗口（子串），使得这个窗口内包含另一个字符串T中的所有字符（包括重复字符）。并不要求子串内字符的顺序与字符串T中的顺序相同。如果S中不存在这样的窗口，则返回空字符串。

下面是对代码的逐行解析：

public class _76最小覆盖子串 {
    Map<Character, Integer> original = new HashMap<Character, Integer>(); // 字符串t中字符的计数
    Map<Character, Integer> count = new HashMap<Character, Integer>(); // 当前窗口中字符的计数

• 定义了两个HashMap，original用于存储字符串T中各字符的计数，count用于动态记录当前“窗口”中各字符的计数。

public String minWindow(String s, String t) {
    // 省略部分代码...

• minWindow是解题的主方法，接收两个字符串s和t作为参数。

if (tLength > sLength || (tLength == sLength && !s.equals(t))){
    return "";
}

• 如果目标字符串t的长度大于源字符串s的长度，或者当两者长度相等但内容不同时，说明不可能覆盖，直接返回空字符串。

for (int i = 0; i < tLength;i++){
    char ch = t.charAt(i);
    original.put(ch,original.getOrDefault(ch,0) + 1);
}

• 初始化originalMap，记录字符串T中每个字符出现的次数。

int left = 0,right = -1;
int len = Integer.MAX_VALUE,resLeft = -1,resRight = -1;

• left和right定义了当前考察的窗口的边界，初始时窗口为空。
• len记录了找到的满足条件的最小子串的长度，resLeft和resRight分别记录了该子串在S中的左右边界索引。

while (right < sLength){ // 主循环，遍历s
    ++right;
    if (right < sLength && original.containsKey(s.charAt(right))){
        count.put(s.charAt(right),count.getOrDefault(s.charAt(right),0) + 1);
    }

• 逐步扩大窗口的右边界，并更新count Map，其中只考虑原字符串T中存在的字符。

while (checkStringEquals() && left <= right){
    if (right - left + 1 < len){
        len = right - left + 1;
        resLeft = left;
        resRight = left + len;
    }
    if (original.containsKey(s.charAt(left))){
        count.put(s.charAt(left),count.getOrDefault(s.charAt(left),0) - 1);
    }
    ++left;
}

• 在确保当前窗口已经包含字符串T的所有字符的前提下，尝试缩小窗口的左边界以找到最短的符合条件的子串。
• 如果当前窗口小于已知的最小长度，则更新最小长度和对应的子串索引。
• 缩小左边界后，相应更新count Map。

return resLeft == -1 ? "":s.substring(resLeft,resRight);
}

• 如果resLeft为-1，说明没有找到符合条件的子串，返回空字符串；否则返回S中的最小窗口。

private boolean checkStringEquals() {
    Iterator iter  = original.entrySet().iterator();
    while (iter.hasNext()) {
        Map.Entry entry = (Map.Entry) iter.next();
        Character key = (Character) entry.getKey();
        Integer val = (Integer) entry.getValue();
        if (count.getOrDefault(key,0) < val){
            return false;
        }
    }
    return true;
}

• checkStringEquals方法用于检查当前窗口是否覆盖了T中的所有字符。
• 通过遍历original Map来确保每个字符的计数都不小于在字符串T中的计数。如果所有字符的计数都大于等于T中对应字符的计数，返回true，否则返回false。

综上所述，这段代码实现了滑动窗口算法来解决最小覆盖子串问题。这是一个典型的双指针滑动窗口问题，其中实时更新窗口内字符的频次，并不断调整窗口大小寻找最小长度的覆盖子串。

参考代码：

_76最小覆盖子串

package leetcode板块;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class _76最小覆盖子串 {
    Map<Character, Integer> original = new HashMap<Character, Integer>(); // 一个哈希表表示 t 中所有的字符以及它们的个数
    Map<Character, Integer> count = new HashMap<Character, Integer>();// 一个哈希表动态维护窗口中所有的字符以及它们的个数
    /**
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        // TODO 滑动窗口 + 字符匹配
        // t为匹配串 ， s为原字符串
        int sLength = s.length(), tLength = t.length();
        //t大于s，或者t不等于s，则直接pass
        if (tLength > sLength || (tLength == sLength && !s.equals(t))){
            return "";
        }
        for (int i = 0; i < tLength;i++){
            char ch = t.charAt(i);
            original.put(ch,original.getOrDefault(ch,0) + 1);
        }
        int left = 0,right = -1;
        //超出t的长度的话，则一定不可能是满足条件的子串
        int len = Integer.MAX_VALUE,resLeft = -1,resRight = -1;
        while (right < sLength){
            ++right;
            if (right < sLength && original.containsKey(s.charAt(right))){
                count.put(s.charAt(right),count.getOrDefault(s.charAt(right),0) + 1);
            }
            // 进行全量字符串检查
            while (checkStringEquals() && left <= right){
                if (right - left + 1 < len){
                    len = right - left + 1;
                    resLeft = left;
                    resRight = left + len;
                }
                if (original.containsKey(s.charAt(left))){
                    count.put(s.charAt(left),count.getOrDefault(s.charAt(left),0) - 1);
                }
                ++left;
            }
        }
        return resLeft == -1 ? "":s.substring(resLeft,resRight);
    }

    /**
     *
     * @return  盘点是否包含了全部的t字符串
     */
    private boolean checkStringEquals() {
        Iterator iter  = original.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            Character key = (Character) entry.getKey();
            Integer val = (Integer) entry.getValue();
            if (count.getOrDefault(key,0) < val){
                return false;
            }
        }
        return true;
    }
}

错误经验吸取