Skip to content

Latest commit

 

History

History
29 lines (19 loc) · 783 Bytes

395.md

File metadata and controls

29 lines (19 loc) · 783 Bytes

395 Longest Substring with At Least K Repeating Characters

Description

link


Solution

简单递归实现,递归过程的条件为:

  • 当出现了小于k个数的字符c时,对str当中的每一段以c为分隔符的substr进行count,由于从上到下有一个max约束,所以最后得到的答案一定是满足题目条件的最大值

Code

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)