# LeetCode395. Longest Substring with At Least K Repeating Characters（递归 / 分治）

## LeetCode395. Longest Substring with At Least K Repeating Characters（递归 / 分治）

• Medium
• Accepted：44,673
• Submissions：116,562

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.

### 链接

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters

### 代码

• Runtime: 176 ms, faster than 34.60% of C++ online submissions for Longest Substring with At Least K Repeating Characters.
• Memory Usage: 54.7 MB, less than 23.08% of C++ online submissions for Longest Substring with At Least K Repeating Characters.
class Solution {
private:
int solve(string s, int k)
{
int n = s.length();
if (n < k)
return 0;
int cnt[26] = {0};
for (int i = 0; i < n; ++i)
cnt[s[i] - 'a']++;
int mid = 0;
while (mid < n && cnt[s[mid] - 'a'] >= k)
++mid;
if (mid == n)
return n;
int left = solve(s.substr(0, mid), k);
int right = solve(s.substr(mid + 1), k);
return max(left, right);
}
public:
int longestSubstring(string s, int k) {
return solve(s, k);
}
};

The end.
2019年4月17日 星期三