# 395. Longest Substring with At Least K Repeating Characters 至少有 K 个重复字符的最长子串

## # 题目描述：

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.
``````

## # 解题方法

1. 如果字符串s的长度少于k，那么一定不存在满足题意的子字符串，返回0；
2. 如果一个字符在s中出现的次数少于k次，那么所有的包含这个字符的子字符串都不能满足题意。所以，应该去不包含这个字符的子字符串继续寻找。这就是分而治之的思路，返回不同子串的长度最大值。
3. 如果s中的每个字符出现的次数都大于k次，那么s就是我们要求的字符串。

``````class Solution(object):
def longestSubstring(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
if len(s) < k:
return 0
for c in set(s):
if s.count(c) < k:
return max(self.longestSubstring(t, k) for t in s.split(c))
return len(s)
``````

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/discuss/87768/4-lines-Python

## # 日期

2018 年 9 月 27 日 —— 国庆9天长假就要开始了！