简单递归实现,递归过程的条件为:
- 当出现了小于k个数的字符c时,对str当中的每一段以c为分隔符的substr进行count,由于从上到下有一个max约束,所以最后得到的答案一定是满足题目条件的最大值
O(n)
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
ctr = collections.Counter(s)
for c, v in ctr.items():
if v < k:
return max([self.longestSubstring(sub, k) for sub in s.split(c) if len(sub)>=k] or [0])
return len(s)