LeetCode.76.最小覆盖子串（困难）

题目

LeetCode.76.最小覆盖子串（困难）

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

注意：

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

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

题解

暴力朴素法

设s长度为n，t长度为m。

把t的字符都存在哈希表中，相同字符进行计数。

从s的每一个位置开始，看后面的m个字符是否都在哈希表中，并且相同字符的个数也一样。

这样匹配的时间复杂度是O(mn)，空间复杂度O(m)。

滑动窗口

暴力法有很多重复的判断，所以时间复杂度高，如果能把已经判断过的东西不用再判断了就可以降低时间复杂度。

可以使用滑动窗口，最多也就是滑动窗口的左右边界走完整个字符串，时间复杂度是O(n)的。

算法步骤：

1. 不停的扩大窗口，直至窗口中包含了t中所有字符。
2. 不停的缩小窗口，直至窗口中没有包含t中所有字符。
3. 重复上述两步，每一步记录最小的窗口的大小。

还是需要把t的字符都存在哈希表中，方便判断窗口中有没有包含t中所有字符，相同字符进行计数。

细节见源码注释。

class Solution {
    /*
    滑动窗口两步走:
    1. 不停的扩大窗口，直至窗口中包含了t中所有字符；如果不能再扩大了就不扩大了
    2. 不停的缩小窗口，直至窗口中没有包含t中所有字符，缩小前记录最小的符合答案条件的子串
     */
    fun minWindow(s: String, t: String): String {
        // S中包含T所有字符的最小子串
        var minSubstr = ""
        val window = Window(s, t)
        while (window.extend()) {
            while (window.match()) {
                // 有更小的满足答案的窗口，那就要记录下来
                // 但是初始时minSubstr是长度为0，需要特殊对待，因为一旦发现了满足答案的窗口，就要更新记录
                if (minSubstr.isEmpty() || window.windowSize() < minSubstr.length) {
                    minSubstr = window.windowString()
                }
                window.shorten()
            }
        }
        return minSubstr
    }

    class Window(
            private val s: String,
            private val t: String
    ) {
        // 记录t中所有字符出现的次数
        private val tMap = mutableMapOf<Char, Int>()

        // 记录窗口已出现的字符的次数，可以只记录t中存在的字符，t中不存在的字符记录也没啥意义
        private val wMap = mutableMapOf<Char, Int>()

        // 记录匹配的字符数量
        private var matchedCharCount = 0

        // 窗口左指针
        private var left = 0

        // 窗口右指针
        private var right = -1

        init {
            t.forEach { c ->
                tMap[c] = 1 + tMap.getOrDefault(c, 0)
            }
        }

        /**
         * 扩大窗口
         *
         * 如果还能继续扩大返回true，不能再扩大了返回false
         */
        fun extend(): Boolean {
            // 窗口已经滑动到字符串最右侧了
            if (right == s.length - 1) return false

            // 扩大窗口
            right++

            // 窗口又增加一个字符
            val c = s[right]

            if (tMap.containsKey(c)) {
                // 窗口只记录t中存在的字符，记录t中不存在的字符也没啥意义
                wMap[c] = 1 + wMap.getOrDefault(c, 0)

                // 如果窗口内当前字符c的个数已经达到t中c字符的数量，记录匹配的字符数量
                // 字符数量过多不管它，在缩小窗口时一起考虑这个问题
                if (tMap.containsKey(c) && tMap[c] == wMap[c]) {
                    matchedCharCount++
                }
            }

            return true
        }

        /**
         * 窗口中有字符串t中所有的字符
         */
        fun match(): Boolean {
            return matchedCharCount == tMap.size
        }

        /**
         * 减少左边界缩短窗口
         */
        fun shorten() {
            val c = s[left]

            if (tMap.containsKey(c)) {
                wMap[c] = wMap.getOrDefault(c, 0) - 1
                // 窗口里c字符数量小于t中c的字符数量，匹配字符数量减1
                // 这里感觉有多减的风险，但是其实不会发生，因为一旦不匹配了，就不会再继续缩小窗口了，而是会扩大窗口，所以不用考虑
                if (wMap[c]!! < tMap[c]!!) {
                    matchedCharCount--
                }
            }

            left++
        }

        /**
         * 窗口字符串长度
         */
        fun windowSize(): Int {
            return right - left + 1
        }

        /**
         * 窗口字符串
         */
        fun windowString(): String {
            return s.substring(left, right + 1)
        }
    }
}