题目描述：

LeetCode 395. Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

题目大意：

给定一个字符串s（只包含小写字母），定义子串T，其中所有字符出现次数均不少于k次，返回子串T的最大长度。

解题思路：

递归（Recursion）/ 分治法（Divide and Conquer）

统计原始字符串s中各字符的出现次数，统计其中出现次数少于k次的字符，得到数组filters。

若filters为空数组，则直接返回s的长度。

以filters为分隔符，将s拆分为若干子串，分别递归计算各子串的结果，返回最大值。

Python代码：

class Solution(object):
    def longestSubstring(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        cnt = collections.Counter(s)
        filters = [x for x in cnt if cnt[x] < k]
        if not filters: return len(s)
        tokens = re.split('|'.join(filters), s)
        return max(self.longestSubstring(t, k) for t in tokens)

 

本文链接：http://bookshadow.com/weblog/2016/09/04/leetcode-longest-substring-with-at-least-k-repeating-characters/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码