LeetCode.076.Minimum Window Substring 最小覆盖子串

题目描述

76 Minimum Window Substring
https://leetcode-cn.com/problems/minimum-window-substring/

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:
If there is no such window in S that covers all characters in T, return the empty string “”.
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

---

相似题目

LeetCode.076.Minimum Window Substring 最小覆盖子串
LeetCode.003.Longest Substring Without Repeating Characters 最长非重复子串
LeetCode.209.Minimum Size Subarray Sum 长度最小的子数组

---

解题过程

滑动窗口法的经典题目，从本题中可以学到如何进行窗口的扩张和收缩。

双指针 left, right 组成滑动窗口闭区间 [left, right]， 哈希表 windowMap 记录窗口内元素的个数，哈希表 tMap 记录目标串 t 的元素个数。
下面是 3 个非常关键的问题？
1、何时扩张滑动窗口右边界 right？ 当窗口内元素还无法覆盖 t 内元素时，扩张右边界 right
2、何时收缩滑动窗口左边界 left？ 当窗口内元素可以覆盖 t 内元素时，尝试收缩窗口左边界 left，直到再一次无法覆盖 t，此后继续扩张右边界 right
3、何时更新最小覆盖子串 minCoverStr？当找到一个覆盖 t 的窗口时，更新 minCoverStr，并且每次收缩左边界 left 后如果还能覆盖 t，继续更新 minCoverStr

LeetCode 官方题解中的这个动图形象的展示了滑动窗口的扩张和收缩过程

滑动窗口

遍历 s 串需要 O(m) 时间复杂度，每次需要 O(n) 复杂度对比两个哈希表。
时间复杂度 O(mn)，空间复杂度 O(m+n)

private static class SolutionV202005 {
    public String minWindow(String s, String t) {
        if (null == t || t.length() < 1 || null == s || s.length() < 1 || s.length() < t.length()) {
            return "";
        }
        // t 串 Map
        Map<Character, Integer> tMap = new HashMap<>();
        for (char ch: t.toCharArray()) {
            tMap.put(ch, tMap.getOrDefault(ch, 0) + 1);
        }
        // 窗口内元素 Map
        Map<Character, Integer> windowMap = new HashMap<>();
        // 最小覆盖子串
        String minCoverStr = "";

        char[] schars = s.toCharArray();
        for (int left = 0, right = 0; right < schars.length; right++) {
            // 扩张右边界 right
            windowMap.put(schars[right], windowMap.getOrDefault(schars[right], 0) + 1);
            if (contain(windowMap, tMap)) {
                // 窗口内元素已覆盖 t，更新最小覆盖子串，并收缩窗口，右移左边界 left，直到窗口无法覆盖 t
                do {
                    // 更新最小覆盖子串
                    if (minCoverStr.equals("") || right - left + 1 < minCoverStr.length()) {
                        minCoverStr = s.substring(left, right + 1);
                    }
                    int count = windowMap.get(schars[left]);
                    if (count > 1) {
                        windowMap.put(schars[left], count - 1);
                    } else {
                        windowMap.remove(schars[left]);
                    }
                    left++;
                } while (contain(windowMap, tMap));
            }
        }
        return minCoverStr;
    }

    // tMap 中 key 都在 sMap 中，且对应 value 大于等于 tMap 中 value 时返回 true
    private boolean contain(Map<Character, Integer> sMap, Map<Character, Integer> tMap) {
        for (Map.Entry<Character, Integer> entry : tMap.entrySet()) {
            if (sMap.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
                return false;
            }
        }
        return true;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_076_MinimumWindowSubstring.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_076_MinimumWindowSubstring.java

---