LeetCode-76-最小覆盖子串

76. 最小覆盖子串

难度困难1164收藏分享切换为英文接收动态反馈

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

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

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

示例 2：

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

提示：

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

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

图示
以S="DOABECODEBANC"，T="ABC"为例
初始状态：

image-20210523113821323

步骤一：不断增加j使滑动窗口增大，直到窗口包含了T的所有元素，need中所有元素的数量都小于等于0，同时needCnt也是0

image-20210523113842794

步骤二：不断增加i使滑动窗口缩小，直到碰到一个必须包含的元素A，此时记录长度更新结果

image-20210523113915069

步骤三：让i再增加一个位置，开始寻找下一个满足条件的滑动窗口

image-20210523114013473

class Solution {
    public static String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        char[] str = s.toCharArray();
        char[] target = t.toCharArray();
        int[] map = new int[256];
        for (char cha : target) {
            map[cha]++;
        }
        int all = target.length;//目标字符串一共有多少个字符
        int L = 0;
        int R = 0;
        
        int minLen = -1;// -1(从来没找到过合法的)
        int ansl = -1;//返回最小的串的L位置
        int ansr = -1;//返回最小的串的R位置
        // [L..R)   [0,0)  R
        while (R != str.length) {
            map[str[R]]--;//遇到一个字符，表示需要的字符数 减-
            if (map[str[R]] >= 0) {//属于目标字符，因为一开始目标字符 >0
                all--;
            }
            if (all == 0) {//完成了步骤一，已经满足target要求
                while (map[str[L]] < 0) {
                    map[str[L++]]++;
                }
                if (minLen == -1 || minLen > R - L + 1) {//更小的minLen
                    minLen = R - L + 1;
                    ansl = L;
                    ansr = R;
                }
                //程序执行到这里，遇到了target字符，all++ ,对应字符++，开始寻找下一个满足条件的滑动窗口
                all++;      
                map[str[L++]]++;
            }
            R++;
        }
        return minLen == -1 ? "" : s.substring(ansl, ansr + 1);
    }
}

image-20210523114153489