题目描述
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.
Example1:
Input: s = "aaabb", k = 3 Output: 3 The longest substring is "aaa", as 'a' is repeated 3 times.
Example2:
Input: s = "ababbc", k = 2 Output: 5 The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
解题思路
- 分治
- 参考
class Solution {
public:
int longestSubstring(string s, int k) {
if(s.size() == 0 || k > s.size()){
return 0;
}
if(k == 0){
return s.size();
}
unordered_map<char, int> mmap;
for(auto c : s){
mmap[c]++;
}
int l = 0;
int n = s.size();
while(l < n && mmap[s[l]] >= k){
l++;
}
if(l == n){
return n;
}
int left = longestSubstring(s.substr(0, l), k);
while(l < n && mmap[s[l]] < k){
l++;
}
if(l == n){
return left;
}
int right = longestSubstring(s.substr(l), k);
return max(left, right);
}
};
