至少有 K 个重复字符的最长子串——分治算法，不太容易想到

"""
分治，怎么分？怎么治？
分：以窗口内出现次数<k的字符为分割点，直到窗口<1或窗口所有字符出现次数>=k则是有效窗口
治：分下去的每个小窗口返回长度，计算最大的返回
每一次分的时候这个分割点，有没可能在下一层的递归中遇到？不会。
因为一段子区间最多有26个字符，就算每个字符递归一次，也就是26，所以递归深度最多26。
而窗口长度最长n，所以时间还是O(n)
"""

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if len(s) < k:
            return 0
        for c in set(s):
            #  "aaabb".count("a") = 3
            if s.count(c) < k:
                # "aaabb".split("a") = ['', '', '', 'bb']
                return max(self.longestSubstring(t, k) for t in s.split(c))
        return len(s)