33.最小覆盖子串

题目

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

注意:

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

示例 1:

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2:

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

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

提示:

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

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

思路

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

整体策略: 双指针先扩张找到合法窗口，再收缩求最短:

right不断右移扩张窗口，直到窗口覆盖了t的所有字符
一旦覆盖，left右移收缩窗口，在仍然覆盖的前提下尽可能缩短
收缩过程中不断记录最短的那个窗口
缩到不再覆盖时，回到第1步继续右移right，寻找下一个合法窗口

这就是求最短型滑动窗口的标准节奏: 右扩到合法，左缩到极限，全程记最短

核心难点: 如何O(1)判断窗口已覆盖t?

朴素做法是每次都把窗口的词频表和t的词频表整个对比一遍，但是这样每次判断都要O(字符集)的开销，拖慢整体。

关键的技巧: 引入valid计数器，把是否覆盖的判断降到O(1)

我们需要维护三样东西:

need : t中每个字符需要的数量
window : 当前窗口里每个字符的实际数量
valid : 已经数量达标的字符种类数

判断逻辑:

当某字符c入窗后，恰好window[c] == needc，就valid++
当valid == need.size(所有种类都达标)，窗口就完整覆盖了t

这样是否覆盖只需要比较两个整数valid == need.size，O(1)完成

class Solution {
    fun minWindow(s: String, t: String): String {
        // 边界：s 比 t 还短，或 t 为空，不可能覆盖
        if (s.length < t.length || t.isEmpty()) {
            return ""
        }

        // need: t 中每个字符需要的数量（需求账本）
        val need = HashMap<Char, Int>()
        for (c in t) {
            need[c] = need.getOrDefault(c, 0) + 1
        }

        var left = 0
        // 当前窗口内每个字符的数量
        val window = HashMap<Char, Int>()
        // 已「数量达标」的字符种类数
        var valid = 0

        // 记录最优解：起点 start + 最短长度 minLen，因为left一直在变，而start是最优解时的left
        var start = 0
        var minLen = Int.MAX_VALUE

        for (right in s.indices) {
            // ===== 扩张：右边字符 c 入窗 =====
            val c = s[right]
            // 只关心 t 里有的字符
            if (need.containsKey(c)) {
                window[c] = window.getOrDefault(c, 0) + 1
                // 该字符「刚好」达标
                if (window[c] == need[c]) {
                    valid++
                }
            }

            // ===== 收缩：窗口已覆盖 t（valid 达标）就尝试缩短 =====
            while (valid == need.size) {
                // 收缩前先记录：此刻窗口是合法的，可能是更优解
                if (right - left + 1 < minLen) {
                    start = left
                    minLen = right - left + 1
                }

                // 移出最左字符 d
                val d = s[left]
                left++
                if (need.containsKey(d)) {
                    if (window[d] == need[d]) {
                        // 移出后将「跌破」达标线
                        valid--
                    }
                    window[d] = window[d]!! - 1
                }
            }
        }

        return if (minLen == Int.MAX_VALUE) "" else s.substring(start, start + minLen)
    }
}

下一题

邮箱：charon.chui@gmail.com
Good Luck!