最小覆盖子串

力扣 76. 最小覆盖子串

题目说明

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

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

示例

示例 1:

1 2	输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC"

示例 2:

1 2	输入：s = "a", t = "a" 输出："a"

示例 3:

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

笔者理解

此题是一道字符串算法问题，在力扣题库中被定义为困难题。

解法

当笔者阅读完此题后，直接采用滑动窗口的方法，先向右延展确定一个最小符合右边界，然后收缩左边界，让我们来看看具体如何实现的吧。

实现

class Solution {
    /**
     * 滑动窗口
     * 字符串
     */
    public String minWindow(String s, String t) {
        Map<Character, Integer> needMap = new HashMap<Character, Integer>();
        Map<Character, Integer> windowsMap = new HashMap<Character, Integer>();

        // 将目标字符串的所有字符记录到needMap中
        for (char c : t.toCharArray()) {
            needMap.put(c, needMap.getOrDefault(c, 0) + 1);
        }

        // 记录窗口的左右边界
        int left = 0, right = 0;

        // 记录窗口中符合 needMap 条件的字符数量
        int valid = 0;

        // 记录最小覆盖子串的起始结尾索引和长度
        int start = 0, len = Integer.MAX_VALUE;

        while (right < s.length()) {

            // 找到入窗口的元素
            char c = s.charAt(right);

            // 右移窗口
            right++;

            // 更新窗口内的数据
            if (needMap.containsKey(c)) {
                windowsMap.put(c, windowsMap.getOrDefault(c, 0) + 1);
                
                // 如果该字符全部被涵盖，则 valid 加一
                if (windowsMap.get(c).equals(needMap.get(c))) {
                    valid++;
                }
            }
            // 判断左侧窗口是否需要收缩
            while (valid == needMap.size()) {

                // 首先更新最小覆盖子串的索引和长度
                // right 自增过一次
                if (right - left < len) {
                    len = right - left;
                    start = left;
                }

                // 找到出窗口的元素
                char d = s.charAt(left);

                // 窗口右移
                left++;

                // 更新窗口中的数据
                if (windowsMap.containsKey(d)) {
                    // 刚好移除左端点元素后, 滑动窗口不包含目标字符串了
                    if (windowsMap.get(d).equals(needMap.get(d))) {
                        valid--;
                    }
                    windowsMap.put(d, windowsMap.getOrDefault(d, 0) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}