LeetCode-76. 最小覆盖子串

题目来源

76. 最小覆盖子串

题目详情

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

注意：

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

示例 1：

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

示例 2：

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

示例 3:

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

提示：

• 1 <= s.length, t.length <= 105
• s 和 t 由英文字母组成

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

题解分析

解法一：双指针法

滑动窗口的思想：

用i,j表示滑动窗口的左边界和右边界，通过改变i,j来扩展和收缩滑动窗口，可以想象成一个窗口在字符串上游走，当这个窗口包含的元素满足条件，即包含字符串T的所有元素，记录下这个滑动窗口的长度j-i+1，这些长度中的最小值就是要求的结果。

步骤一

不断增加j使滑动窗口增大，直到窗口包含了T的所有元素

步骤二

不断增加i使滑动窗口缩小，因为是要求最小字串，所以将不必要的元素排除在外，使长度减小，直到碰到一个必须包含的元素，这个时候不能再扔了，再扔就不满足条件了，记录此时滑动窗口的长度，并保存最小值

步骤三

让i再增加一个位置，这个时候滑动窗口肯定不满足条件了，那么继续从步骤一开始执行，寻找新的满足条件的滑动窗口，如此反复，直到j超出了字符串S范围。

如何判断滑动窗口包含了T的所有元素？

1. 对于如何判断滑动窗口中包含所有元素，我们可以使用一个整数数组，类似于以前做过的和。
2. 这里可以优化的一个地方就是，如果单纯使用cnts数组计数每个字符出现的次数，那么在判断的时候每次都需要判断数组中所有元素的数量都小于等于0时，表示当前滑动窗口不再需要任何元素。
3. 具体地，我们可以再使用一个计数指针cnt表示目标串中总共需要计数的字符数，并在滑动窗口的过程中维护该变量。最后，只需要判断cnt是否为0即可。

class Solution {
    public String minWindow(String s, String t) {
        int n = t.length();
        int cnt = n;// 记录目标串所有字符出现的总次数
        int l=0, r=0;// 双指针的左右边界
        int[] cnts = new int[128];// 记录某个英文字母（大小写字母最大ascii码为126）出现的次数
        for(int i=0; i 0){// 需要该字符
                cnt--;
            }
            cnts[ch]--;// 计数该字符，所需字符数量减一
            if(cnt == 0){// 窗口中已经包含目标串中的所有字符
                while(l < r && cnts[s.charAt(l)] < 0){// 不断向右移动左指针，但始终保持窗口中含有目标串的所有字符
                    cnts[s.charAt(l)]++;// 释放左指针所在字符
                    l++;
                }
                if(r - l + 1 < minsize){
                    minsize = r - l + 1;
                    ans = s.substring(l, r + 1);
                }
                // 左指针再向右移动一个位置，那么窗口中肯定不满足条件
                cnts[s.charAt(l)]++;
                l++;
                cnt++;
            }
            r++;// 右指针右移
        }
        return ans;
    }
}

结果展示