「力扣」第 76 题：最小覆盖子串

发布日期: 2017-06-20

中文网址：76. 最小覆盖子串；
英文网址：76. Minimum Window Substring 。

给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：

如果 S 中不存这样的子串，则返回空字符串 ""。

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

说明：这道题被「力扣」标记为「困难」。

1、只关心频数，不关心顺序，因此我们需要记录频次；

2、定义「距离」，编辑距离，汉明距离；

3、子串左边和右边都不能是不相关的字符；

4、字符数可以多，但不能少。

题目中的这个例子得改一下 XYZADOBECODEBANC。

Java 代码：加法，用数组。

public class Solution {

    public String minWindow(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if (sLen == 0 || tLen == 0 || sLen < tLen) {
            return "";
        }

        int[] countS = new int[256];
        int[] countT = new int[256];
        char[] charArrayS = s.toCharArray();
        char[] charArrayT = t.toCharArray();

        int distance = 0;
        for (char charT : charArrayT) {
            if (countT[charT] == 0) {
                distance++;
            }
            countT[charT]++;
        }

        int count = 0;
        int begin = 0;
        int minLen = sLen + 1;
        for (int left = 0, right = 0; right < sLen; ) {
            if (countT[charArrayS[right]] == 0) {
                right++;
                continue;
            }

            countS[charArrayS[right]]++;
            if (countS[charArrayS[right]] == countT[charArrayS[right]]) {
                count++;
            }
            right++;

            while (count == distance) {
                // 这里位置还可以靠后
                if (right - left < minLen) {
                    minLen = right - left;
                    begin = left;
                }

                if (countT[charArrayS[left]] > 0) {
                    countS[charArrayS[left]]--;
                    if (countS[charArrayS[left]] < countT[charArrayS[left]]) {
                        count--;
                    }
                }
                left++;
            }
        }

        if (minLen == sLen + 1) {
            return "";
        }
        return s.substring(begin, begin + minLen);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String S = "ADOBECODEBANC";
        String T = "ABC";
        String minWindow = solution.minWindow(S, T);
        System.out.println(minWindow);
    }
}

Java 代码：减法，用哈希表。

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

public class Solution {

    public String minWindow(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if (sLen == 0 || tLen == 0 || sLen < tLen) {
            return "";
        }

        Map<Character, Integer> countT = new HashMap<>();
        char[] charArrayT = t.toCharArray();
        for (char c : charArrayT) {
            countT.put(c, countT.getOrDefault(c, 0) + 1);
        }
        int distance = countT.size();


        int minLen = sLen + 1;
        int left = 0;
        int right = 0;
        int begin = 0;

        char[] charArrayS = s.toCharArray();
        while (right < sLen) {
            // 调试代码
            // System.out.println(s.substring(left, right));
            // System.out.println(countT);

            Integer countRight = countT.get(charArrayS[right]);
            if (countRight == null) {
                right++;
                continue;
            }

            countRight--;
            countT.put(charArrayS[right], countRight);
            if (countRight == 0) {
                distance--;
            }
            right++;

            while (distance == 0) {
                Integer countLeft = countT.get(charArrayS[left]);
                if (countLeft == null) {
                    left++;
                    continue;
                }
                countLeft++;
                countT.put(charArrayS[left], countLeft);
                if (countLeft > 0) {
                    distance++;
                }

                if (right - left < minLen) {
                    minLen = right - left;
                    begin = left;
                }
                left++;
            }
        }

        if (minLen == sLen + 1) {
            return "";
        }
        return s.substring(begin, begin + minLen);
    }
}

Java 代码：

public class Solution {

    public String minWindow(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if (sLen == 0 || tLen == 0) {
            return "";
        }

        int[] countS = new int[256];
        int[] countT = new int[256];
        char[] charArrayS = s.toCharArray();
        char[] charArrayT = t.toCharArray();

        int distance = 0;
        for (char charT : charArrayT) {
            if (countT[charT] == 0) {
                distance++;
            }
            countT[charT]++;
        }

        int minLen = sLen + 1;
        int left = 0;
        int right = 0;
        int count = 0;
        int begin = 0;
        while (right < sLen) {
            if (countT[charArrayS[right]] == 0) {
                right++;
                continue;
            }

            countS[charArrayS[right]]++;
            if (countS[charArrayS[right]] == countT[charArrayS[right]]) {
                count++;
            }
            right++;

            while (count == distance) {
                if (right - left < minLen) {
                    minLen = right - left;
                    begin = left;
                }

                if (countT[charArrayS[left]] > 0) {
                    countS[charArrayS[left]]--;
                    if (countS[charArrayS[left]] < countT[charArrayS[left]]) {
                        count--;
                    }
                }
                left++;
            }
        }

        if (minLen == sLen + 1) {
            return "";
        }
        return s.substring(begin, begin + minLen);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String S = "ADOBECODEBANC";
        String T = "ABC";
        String minWindow = solution.minWindow(S, T);
        System.out.println(minWindow);
    }
}

for 循环写法：

Java 代码：

public class Solution {

    public String minWindow(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if (sLen == 0 || tLen == 0) {
            return "";
        }

        int[] countS = new int[256];
        int[] countT = new int[256];
        char[] charArrayS = s.toCharArray();
        char[] charArrayT = t.toCharArray();

        int distance = 0;
        for (char charT : charArrayT) {
            if (countT[charT] == 0) {
                distance++;
            }
            countT[charT]++;
        }

        int minLen = sLen + 1;
        int count = 0;
        int begin = 0;
        for (int left = 0, right = 0; right < sLen; ) {
            if (countT[charArrayS[right]] == 0) {
                right++;
                continue;
            }

            countS[charArrayS[right]]++;
            if (countS[charArrayS[right]] == countT[charArrayS[right]]) {
                count++;
            }
            right++;

            while (count == distance) {
                if (right - left < minLen) {
                    minLen = right - left;
                    begin = left;
                }

                if (countT[charArrayS[left]] > 0) {
                    countS[charArrayS[left]]--;
                    if (countS[charArrayS[left]] < countT[charArrayS[left]]) {
                        count--;
                    }
                }
                left++;
            }
        }

        if (minLen == sLen + 1) {
            return "";
        }
        return s.substring(begin, begin + minLen);
    }
}

Java 代码：

import java.util.HashSet;
import java.util.Set;

public class Solution {

    // 参考资料：https://blog.csdn.net/feliciafay/article/details/44535301
    // 先复习第 438 题再做这题可能会好些
    // 滑动窗口，这个问题有一些难
    public String minWindow(String s, String t) {
        int[] cntS = new int[256];
        int[] cntT = new int[256];

        Set<Character> set = new HashSet<>();
        // cntT 赋值了以后，就成为了用于比对的对象，不更新
        for (char ct : t.toCharArray()) {
            cntT[ct]++;
            set.add(ct);
        }

        int minSub = s.length() + 1;
        String res = "";
        // 滑动窗口左边界
        int left = 0;
        // 滑动窗口右边界
        int right = 0;

        // 逻辑：右边界进来的时候，数组 s 的次数都加 1

        int count = 0;
        while (right < s.length()) {
            char rc = s.charAt(right);
            if (!set.contains(rc)) {
                // 不在字典里面，但是右边界同样要扩充，所以 right++
                right++;
                continue;
            }
            cntS[rc]++;
            right++;
            // 理解这里是关键：加上以后，小于等于，count 才 ++，
            if (cntS[rc] <= cntT[rc]) {
                // count++; 这件事情说明滑动窗口里面的有效字符，向目标字符又近了一步
                count++;
            }

            // 下面这一段可以写得更精简一些，但是为了语义上的清晰，我就写得冗长一些
            if (count == t.length()) {
                // 接下来，考虑左边界移出滑动窗口
                // 不在字典中，或者多了的时候，直接划掉就可以了
                while (true) {
                    char deleteChar = s.charAt(left);
                    if (!set.contains(deleteChar)) {
                        left++;
                        continue;
                    }
                    if (cntS[deleteChar] > cntT[deleteChar]) {
                        cntS[deleteChar]--;
                        left++;
                        continue;
                    }
                    break;
                }
                if (right - left < minSub) {
                    minSub = right - left;
                    res = s.substring(left, right);
                }
            }
        }
        if (minSub == s.length() + 1) {
            return "";
        }
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String S = "ADOBECODEBANC";
        String T = "ABC";
        String minWindow = solution.minWindow(S, T);
        System.out.println(minWindow);
    }
}

（本节完）

方法一：暴力求解

以 输入: S = "ADOBECODEBANC", T = "ABC" 为例，由于 T 中所有的字符都互不相同。我们可以：

1、枚举 S 中长度大于等于 3 的所有子串；

2、对这些子串逐个判断是否包含 T 的所有字母。

3、对满足上述两条的所有子串，取最小值。

枚举所有子串，$O(N^2)$ ，判断是否包含 T 的所有字符，$O(N)$。总体的时间复杂度是 $O(N^3)$。

方法二：滑动窗口

下面我们思考如何优化：

1、一开始的时候，left 和 right 都位于 0 的位置，right 向右移动，直至包含 T 的所有字母。因为我们要求的是最小子串，因此，以 left 开头的子串 [left, right + 1]、 [left, right + 2]、……、 [left, len - 1] 一定不符合要求。因此可以不用判断。

2、然后考虑 left 如何移动，left 不能向左移动，向左移动只能让子串更长，我们要求最小子串，因此 left 只能右移，移到 left 滑出以后，恰恰好 [left, right] 这个区间里面的字符不包含 T 所有字母的最小子串。

3、然后 right 继续向右移动，直到包含 T 所有字母的最小子串。

重复这样的过程，直到 right 到达 S 的末尾。怎么样，这个思想是不是和第 3 题是一样的，尺取法。

尺取法有下面的特点：

right 先向右移动，移到不能再移动的时候，left 再向右移动。

right 变长刚好满足条件，left 变短到刚好不满足条件，然后 right 变长刚好满足条件，如此循环下去，直到 right 到达末尾。

这里的条件是指：[left, right) 包含 T 所有字母。

这里如何判断区间 [left, right] 内包含 T 所有字母呢？

由于我们并不关心字母的顺序，因此我们采用的是对比频数数组的方式。

1、先对 T 做频数统计，然后设置一个变量 distance 表示 T 中一共有多少个不同的字母

2、left 和 right 在动的时候，只对 T 中出现的字母做统计。

right 移动的时候，频数增加，加到刚刚好和 T 对应字母相等的时候，distance - 1，表示滑动窗口内的字母种类与 T 的差距减少了 1，当这个差距为 0 的时候，滑动窗口内包含 T 所有字母的最小子串。此时考虑移动 left；

3、left 移动的时候，做减法，减少到刚刚好比 T 中对应字符个数少 1 的时候，就说明“平衡”被打破，此时应该 right 继续向右移动。

1、right 一直往前走，走到 [left, right] 包含 T 里所有的字母。

2、right 和 left 同方向。

3、小技巧：用哈希表或者数组统计不同字母的个数，这样可以保证复杂度最低。

（1）使用数组，会有空隙；

（2）使用哈希表，空隙是动态计算出来的。

Java 代码：

public class Solution {

    public String minWindow(String s, String t) {
        int[] window = new int[128];
        int[] pattern = new int[128];

        final int A = 'A';

        for (Character c : t.toCharArray()) {
            pattern[c - A]++;
        }
        int distance = 0;

        for (int i = 0; i < 128; i++) {
            if (pattern[i] > 0) {
                distance++;
            }
        }

        int sLen = s.length();
        int start = 0;
        int left = 0;
        int right = 0;
        int match = 0;
        int minLen = sLen + 1;

        while (right < sLen) {
            Character curChar = s.charAt(right);
            if (pattern[curChar - A] > 0) {
                window[curChar - A]++;

                if (window[curChar - A] == pattern[curChar - A]) {
                    match++;
                }
            }

            right++;

            while (match == distance) {
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }

                // 考虑左边界向右边走
                Character leftChar = s.charAt(left);
                if (pattern[leftChar - A] > 0) {
                    window[leftChar - A]--;

                    if (window[leftChar - A] < pattern[leftChar - A]) {
                        match--;
                    }
                }
                left++;
            }
        }
        return minLen == sLen + 1 ? "" : s.substring(start, start + minLen);
    }
}

这里还要注意细节：

1、minLen，一开始要设置一个不可能的值；

2、同时记录左边界 left 和 minLen。

与第 3 题对比

1、对于这一题，我们需要时刻关注的是：[left, right) 内包含 T 的所有字母。它就是条件，因此在模板的 ① 处取最小值。

2、用频数数组、哈希表的区别。

这一节介绍的例题中使用两个数组统计频数进行比对的技巧是比较常见的。

总结滑动窗口问题：

1、尺取法：left 和 right 同方向移动；

2、定义条件，即我们需要时刻监测的一件事情；

3、原理：充分利用本题本身的特点，以减少不必要的计算；

4、利用循环不变量保证代码正确性；

5、代码模板，知道什么时候滑动窗口最长，什么时候滑动窗口最短；

6、字符串处理技巧。

练习：

1、「力扣」第 209 题：长度最小的子数组

2、「力扣」第 438 题：找到字符串中所有字母异位词

3、「力扣」第 567 题：字符串的排列

liweiwei1419

https://liweiwei1419.gitee.io/leetcode-algo/2017/06/20/leetcode-algo/0076-minimum-window-substring/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !

滑动窗口

「力扣」第 209 题：长度最小的子数组（中等）

「力扣」第 209 题：长度最小的子数组（中等）中文网址：209. 长度最小的子数组；英文网址：209. Minimum Size Subarray Sum 。给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中

2017-06-21 专题 4：滑动窗口

滑动窗口

「滑动窗口」专题：概述与经典问题

「滑动窗口」专题：滑动窗口的基本思想在滑动窗口类型的问题中都会有两个指针。一个用于延伸现有窗口的 right 指针，和一个用于收缩窗口的 left 指针。在任意时刻，只有一个指针运动，而另一个保持静止。「滑动窗口」的问题其实思想并不难

2017-06-19 专题 4：滑动窗口

二分查找减治思想

「力扣」第 76 题：最小覆盖子串