题解 | #至少有 K 个重复字符的最长子串#

分治法，找到每个不符合的区间再依次向下找直至区间长度小于 k, 比较其中的最大字符串长度

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @param k int整型 
# @return int整型
#
from collections import defaultdict
class Solution:
    def longestSubstring(self , s: str, k: int) -> int:
        # write code here
        def subString(l, r):
            if r - l < k:
                return 0
            count = defaultdict(list)
            flag = True
            for i in range(l, r):
                count[s[i]].append(i)
            data = []
            for i, v in count.items():
                if len(v) < k:
                    flag = False
                    data += v
            if flag:
                return r - l
            data.sort()
            max_l = 0
            data = [l] + data + [r]
            for i in range(1, len(data)):
                if i == 1:
                    max_l = max(subString(data[i - 1], data[i]), max_l)
                else:
                    max_l = max(subString(data[i - 1] + 1, data[i]), max_l)
            return max_l
        return subString(0, len(s))