LeetCode 395 至少有 K 个重复字符的最长子串

Ciel Yang 收录于类别练习 OJ解题报告

2021-03-08 2021-03-08 约 1603 字预计阅读 4 分钟

本题是一道较少见的滑动窗口题目，不能直接套用滑动窗口模板，但是却更考察了对滑动窗口方法的前提的掌握，仔细研究必定能增强对这一解题方法的理解。

题目描述

原题链接如下： LeetCode 395 至少有 K 个重复字符的最长子串

题目大意

假设一个只包含小写字母的字符串 s，其字串可能含有多种字母，如果字串的每种字符数量都超过 k，则是一个合法字串，求最长的合法字串的长度。

输入与输出

示例输入为：

1
2
3
4
5
6
7
Input 1:
s = "aaabb"
k = 3

Input 2:
s = "ababbc"
k = 2

s 的长度区间是 $[1, 10000]$
k 的取值范围是 $[1, 100000]$

对应输出为：

1
2
3
4
5
Output 1:
3

Output 2:
5

解题思路

首先，注意到本题的 k 可能超过 s 的长度，此时答案必定是 0。然后，又有两种不同的解法。

滑动窗口

本题不可以直接套用滑动窗口的模板代码，因为使用不定长度的滑动窗口的模板代码的前提是答案与窗口长度有单调关系：随着窗口的右端点值增加，最优解的左端点位置单调不减。单调性保证了我们的算法可以在 $O(n)$ 时间复杂度遍历所有决策，得出每个右端点对应的最优解，也就能得到数组或字符串的总体最优解。但是本题如果直接套用模板代码，在右端点增加时，却无法保证单调性成立，比如:对于字符串 abba 且 k = 2，窗口如果是字串 bb，那么字串向右扩张时左端点必须向左扩张才能得到正确的最优解。此时，我们甚至无法确定滑动窗口的左端该如何收缩。但是，我们注意到题目的输入数据只有小写字母，范围极小，我们不妨为滑动窗口增加一个条件：窗口内只能刚好包含 x 种字符。显然，x 的取值范围是 $[1, 26]$，要得到原题答案我们只需依次遍历所有可能的 26 个值即可。这样，上述反例类型就不再困扰我们了因为 bb 和 abba 对应 x 为 1 和 2 的两种情况，各自情况下的滑动窗口右端点对应了不同的左端点。实际上，因为窗口的约束条件刚好包含 x 种字符，而且此时：

右端点扩张一定不会减少子串的字符种类
左端点收缩一定不会增加子串的字符种类

所以，我们只要在字符串的字符种类大于 x 的时候收缩窗口即可。另外，不是所有的窗口都符合要求，必须窗口内部所有的字符数量都是大于 k 时才可以。我们可以使用一个长度 26 的数组计数窗口内部字符的数量：

如果字符数量由 0 变为 1，则新增了字符种类，反之则减少了字符种类
如果字符数量由 k - 1 变为 k，则新增了合法字符种类，反之则减少了合法字符种类

这样，只有合法字符种类和总的字符种类相等时，才意味着这个窗口对应着合法子串。

分治法

可以看出如果字符串内的所有字符出现次数都不小于 k 的时候，本题的答案就是字符串的长度。而如果字符串内可能有某些字符出现的总数小于 k 的时候，这些字符一定在合法子串中，那么它们就把原来的字符串分解为一系列子串，我们只要在这些子串中递归寻找它们各自的合法子串，然后确定最长的合法子串长度即可，显然可以使用多路分治法求解本题。另外，注意本题的递归可以进行剪枝处理以减少时间消耗，如：

需要处理的字符串（子串）长度小于 k 时，直接返回 0
需要处理的字符串（子串）的字符出现次数都不小于 k 时，直接返回其长度

另外，所有字符出现次数都小于 k 时答案显然为 0，但是本题的输入数据并不全面，暂时无需对此情况进行剪枝处理。本题每次递归如果要继续深入则至少会移除一种字符，而字符最多也只有 26 种，所以总的时间复杂度为 $O(n)$

代码

滑动窗口解法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    fun longestSubstring(s: String, k: Int): Int {
        if (k > s.length) return 0
        var re = 0
        for (charNum in 1..26) {
            if (charNum > s.length) break
            val bucket = IntArray(26)
            var charTypes = 0
            var validChars = 0
            var l = 0
            for (r in s.indices) {
                val idx = s[r] - 'a'
                bucket[idx]++
                if (bucket[idx] == 1) charTypes++
                if (bucket[idx] == k) validChars++
                while (charTypes > charNum) {
                    val t = s[l++] - 'a'
                    if (bucket[t] == 1) charTypes--
                    if (bucket[t] == k) validChars--
                    bucket[t]--
                }
                if (validChars == charTypes) re = maxOf(re, r - l + 1)
            }
        }
        return re
    }
}

分治法解法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    private var limit = 0
    fun longestSubstring(s: String, k: Int): Int {
        limit = k
        return helper(s, 0, s.length)
    }

    private fun helper(s: String, start: Int, end: Int): Int {
        if (start >= end || start + limit > end) return 0
        val bucket = IntArray(26)
        for (i in start until end) {
            bucket[s[i] - 'a']++
        }
        var prev = start
        var re = 0
        for (i in start until end) {
            if (bucket[s[i] - 'a'] >= limit) continue
            val max = i - prev
            if (max > re) {
                val t = helper(s, prev, i)
                re = maxOf(re, t)
            }
            prev = i + 1
        }
        if (prev == start) return end - start
        return maxOf(re, helper(s, prev, end))
    }
}

目录