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.
Solution1：Divide & Conquer
思路：
Time Complexity: O(N*log底3(N)) Space Complexity: O(N)
Solution2：Divide & Conquer
思路：
Time Complexity: O() Space Complexity: O()
Solution1 Code：
class Solution {
public int longestSubstring(String s, int k) {
if(s == null || s.length() == 0) {
return 0;
}
int[] count = new int[26];
for(int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
}
char gap_c = ' ';
for(int i = 0; i < count.length; i++) {
if(count[i] < k && count[i] > 0) {
gap_c = (char)('a' + i);
break;
}
}
// terminal
if(gap_c == ' ') {
return s.length();
}
// divide
String[] substrs = s.split("" + gap_c);
int[] res = new int[substrs.length];
for(int i = 0; i < substrs.length; i++) {
res[i] = longestSubstring(substrs[i], k);
}
// conquer
int max_len = 0;
for(int i = 0; i < res.length; i++) {
if(res[i] > max_len) {
max_len = res[i];
}
}
return max_len;
}
}
