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

发表于 分类于 阅读次数： 本文字数： 600 阅读时长 ≈ 2 分钟

其实，昨天我就打开了今天的打卡题，看到中等难度，我心里也是一咯噔，毕竟我现在的水平，简单也未必都能做出来的啊。

仔细读了题目意思后，发现，真的是难，超出了我能控制的范围了。晚上睡在床上就在反复推演，这个题目到底应该怎么做，没有什么头绪睡着了，早上起来，马上看答案。原来是用分治法。

这个题目的意思是，找到一个最长的子串，子串里的每个出现的字母，出现频次不少于 K。我真正反思的是，为啥我写不出一个算法，我发现，我就算不用代码，用嘴也不能说清楚，我到底按照怎样的步骤来做这个题目。这里的问题就严重了，如果你能说出一个算法，那可能往往是性能差，效率低，但是终究还是有一个算法的。现在的问题是，我根本连一个算法也拿不出，这就有点困扰了。智商被碾压。

分治法的实际做法是比较朴素的，就是先统计每个字母的出现频次。因为只有小写字母，所以一共就 26 个，这里如果所有的字母频次都大于等于 K，那么整个串的长度就是我们要的解。如果有至少一个字母频次不足 K，我们可以用这个字母来分割字符串。先从第一个分割位置开始，逐一统计每个分割出来的子串的长度，最大的值就是我们的解。

这个解法是递归的，对于每个子串来说，我们也用同样的策略来统计。于是就有了这样的算法：

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
29
30
31
32
33
34
class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        return self.dfs(s, 0, len(s) - 1, k)

    def dfs(self, s: str, l: int, r: int, k: int) -> int:
        freq = collections.Counter()

        for i in range(l, r + 1) :
            freq[s[i]] += 1

        split = '#'
        for i in range(l, r + 1) :
            if freq[s[i]] < k:
                split = s[i]

        if split == '#':
            return r - l + 1

        ret = 0
        i = l
        while i < r:
            while i <= r and s[i] == split:
                i += 1
            
            if i > r :
                break

            start = i
            while i <= r and s[i] != split:
                i += 1

            ret = max(ret, self.dfs(s, start, i - 1, k))
            
        return ret

算法的主体是个深度优先搜索。每次分割，要重新统计里面每个字母的频次，主要因为切割过后，新的子串里的某个字母可能出现了少于 K 次，这就成为了重新切割的依据，这也是说这个解法是递归的原因。

官方题解里，还提到了一个滑动窗口的算法，不过我看了两遍，竟然真的没有理解到底是什么意思。略微崩溃，容我回头再细细体会吧。