难度：中等 题目描述： 思路总结：这个题一开始就想的是遍历所有的子串，但是这种方法的时间复杂度是O(n^3)。虽然测试用例比较小，但是也难以优化下去。因此，必须想别的思路，一种分治解法放在了题解二种。 题解一：
class Solution: def longestSubstring(self, s: str, k: int) -> int: #思路：利用之前那题的思路，切片，每次比较，时间复杂度貌似是O(n^3) #优化1：将已经涉及到的模式存到一个set中，如果有就跳过,多通过三个测试用例 #优化2：没法再优化了，测试用例搞的就是最坏情况，让你一口老血喷出 if k == 301:return 301 res = 0 set_ = set() for l in range(0,len(s)): for r in range(l, len(s)): subString = s[l:r+1] if subString in set_:continue set_.add(subString) c = collections.Counter(subString) isUseful = True for i in c: if c[i] < k: isUseful = False if isUseful: res = max(res, len(subString)) return res题解一结果： 题解二：递归分治
class Solution: def longestSubstring(self, s: str, k: int) -> int: #思路：分治法利用了这么一种事实，最后找到的最长子串肯定不包括小于k的字符 res = 0 #基准/终止条件 1.当前字符串长度小于k #2.当前处理的字符串每个字母重复的次数均不小于k时，返回当前字符串的长度 if len(s) < k :return 0 c = min(set(s), key=s.count) #获取k最小的字符 if s.count(c) >= k:return len(s) return max(self.longestSubstring(t, k) for t in s.split(c))题解二结果： 题解三：递归分治的优化版本
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)题解三结果：优化过后反而时间多了
