• ㊗️
• 大家
• offer
• 多多！

## Problem

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

Example 1:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.


Example 2:

Input: s = "ababbc", k = 2
Output: 5
Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.


## Code

class Solution {
public int longestSubstring(String s, int k) {
return helper(s.toCharArray(), 0, s.length(), k);
}

private int helper(char[] str, int start, int end, int k){
// 停止条件是字符串的长度小于k
if(end - start < k) {
return 0;
}

int[] count = new int[26];

// 统计字符串
for(int i = start; i < end; i++){
int idx = str[i] - 'a';
count[idx]++;
}

// 这样遍历字母的原因是只要遍历到不满足条件的字符就会找到答案
// 答案一定在左边或者右边
for(int i = 0; i < 26; i++){
// 下面这个是不满足要求的字符, 它不能出现在任何有效的子字符串中
if(count[i] < k && count[i] > 0){
// 需要找到这个字符的位置, 然后分别求解它的左半部分和右半部分
for(int j = start; j < end; j++){
if(str[j] == i + 'a'){
int left = helper(str, start, j, k);
int right = helper(str, j + 1, end, k);
return Math.max(left, right);
}
}
}
}

// 用于返回有效的子字符串, 即每个字符都是满足条件的，
// 没有在for循环return
return end - start;
}
}