至少有k个重复字符的最长字串

Leetcode Link: 395. 至少有 K 个重复字符的最长子串 - 力扣（LeetCode）

题目

解法一

思路： 分治

假设这样一种情况：我们发现其中一个字符 c 在字符串 s 中的个数不足 k 个，可以怎么做？

我们可以将字符串 s 以 c 为分界分隔成若干个子字符串，然后就变成了子问题，可以递归完成。

那我们什么时候可以停止递归？ 显然，当当前字符串的长度小于k，一定不能满足题目要求了，因此返回0。

题解：

class Solution(object):
    def longestSubstring(self, s, k):
	    # base case
        if len(s) < k:
            return 0
        # 找子问题并分治递归
        for c in set(s):
            if s.count(c) < k:
                return max(self.longestSubstring(t, k) for t in s.split(c))
        return len(s)

本题的一个小提醒

可以看到上面的代码里，我们虽然遍历了 s，但是我们在遇到的第一个数量小于 k 的 c 就进行了分治递归，并且立刻返回了结果。 即我们没有考虑其他的数量小于 k 的字符。 这是可以的，假设第一个数量小于 k 的字符是 a。我们可以确定满足题目要求的字符串一定不含有 a，所以我们不需要在同一层继续遍历下去了，只需要在子问题里处理子字符串即可。 在进行分治时，这个想法要时刻谨记：我们有没有必要在同一层要找到所有可能的子问题？即子问题的重叠情况。

解法二

思路： 【宫水三叶の相信科学系列】为什么不能用「滑动窗口」？以及如何发掘题目性质 - 至少有 K 个重复字符的最长子串 - 力扣（LeetCode）

题解：

解法三

思路：

题解：

启发和联系

类似问题无重复字符串的最长子串