LeetCode百题【最小覆盖子串】

题目描述

给你一个字符串 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 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

1 <= s.length, t.length <= 10^5
s 和 t 由英文字母组成

进阶： 你能设计一个在 o(n) 时间内解决此问题的算法吗？

解法

滑动窗口
- 一个用于「延伸」现有窗口的 r指针
- 一个用于「收缩」窗口的 l指针
- 在任意时刻，只有一个指针运动，而另一个保持静止。我们在 s上滑动窗口，通过移动 r指针不断扩张窗口。
- 当窗口包含 t全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。

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

class Solution {
    Map<Character, Integer> sMap = new HashMap<>();//遍历过程中具体出现的子串kv关系表
    Map<Character, Integer> tMap = new HashMap<>();//key:字符 v出现次数

    public String minWindow(String s, String t) {
        int tLen = t.length();
        int sLen = s.length();
        //1.定义返回结果所需变量
        int ans_left = -1; //最短子左下标
        int ans_right = -1;//最短子串右下标
        int ans_len = Integer.MAX_VALUE;//最短子串长度
        int left = 0, right = -1;//滑动窗口的左右指针
        //2.存储tMap的kv关系
        for (int i = 0; i < tLen; i++) {
            char c = t.charAt(i);
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }
        //3.滑动窗口进行判定
        while (right < sLen) {
            right++;
            //移动右指针，并判断当前字符如果是子串含有的，有就进行相应计数
            if (right < sLen && tMap.containsKey(s.charAt(right))) {
                char key = s.charAt(right);
                sMap.put(key, sMap.getOrDefault(key, 0) + 1);
            }
            //右移后检查子串是否符合要求
            //  符合条件->准备缩短子串 左指针右移
            //  缩短是个持续的过程，所以用循环
            while (check() && left <= right) {
                //满足条件且比之前答案的长度要小，更新
                if (right - left + 1 < ans_len) {
                    ans_len = right - left + 1;//更新长度
                    ans_left = left;//更新左下标
                    ans_right = right + 1;//更新右下标
                }
                //左指针右移之前，如果左指针包含了子串有的字符，移动之前更新的哈希表
                if (tMap.containsKey(s.charAt(left))) {
                    Character key = s.charAt(left);
                    sMap.put(key, sMap.getOrDefault(key, 0) - 1);
                }
                left++;
            }
        }
        return ans_left == -1 ? "" : s.substring(ans_left, ans_right);
    }
    /**
     * 检查当前子串是否包含所需子串的所有字符
     *
     * @return
     */
    public boolean check() {
        for (Map.Entry<Character, Integer> tEntry : tMap.entrySet()) {
            Character key = tEntry.getKey();
            Integer value = tEntry.getValue();
            if (sMap.getOrDefault(key, 0) < value) {
                return false;
            }
        }
        return true;
    }
}