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

题目

思路

分治法

统计字符串中的各个字符，对于不满足出现k次的字符依次切分字符串s；并对切分后的字符串片段递归判断是否满足条件

code

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        
        def helper(s):
            if not s:
                return 0
            letters = set(s) # 单独分出s中的各个字母
            for l in letters:
                if s.count(l) < k: # 需要过滤的字母
                    ss = s.split(l) 
                    # helper 会递归判断需要过滤的字符
                    return max([helper(i) for i in ss])
            # 如果都满足条件，返回字符串s本身的长度
            return len(s)
             
        return helper(s)