leetcode [395] 至少有K个重复字符的最长子串

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。

示例 1:

输入:
s = "aaabb", k = 3

输出:
3

最长子串为 "aaa" ，其中 'a' 重复了 3 次。

示例 2:

输入:
s = "ababbc", k = 2

输出:
5

最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

来自题解:

递归的两个条件

基线条件

• 当前处理的字符串每个字母重复的次数均不小于k时，返回当前字符串的长度
• 当前字符串长度小于k，返回0

递归条件

当前处理的字符出现的次数小于k，以当前字符为分隔符切割当前字符串，对切割好的子字符串依次调用函数本身

更新条件

递归会把字符串s一次次的切分，直到出现s.count(c) >= k或len(s) < k的情况，而每次由大到小的切分，都可能出现满足类型2的s2字符串出现。 那么动态规划部分要做的就是，与历史最长的s2长度比较，然后更新，直到迭代完整个字符串

结果：max([len(s2) for s2 in s2_list])

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        for c in set(s):
            if s.count(c) < k:
                # 满足分割条件，进行分割
                return max(self.longestSubstring(t, k) for t in s.split(c))
        # 如果每个字符出现的次数均不小于k，则返回当前字符串的长度
        return len(s)