class Solution {
public:
int longestSubstring(string s, int k) {
return dfs(s,k);
}
int dfs(string s,int k ){ //求字符串中最长的每个字符都不少k的子串长度
int cnt[26] = {0};
for(int i = 0;i < s.size();i++){ //统计每个字符出现的次数
cnt[s[i]-'a']++;
}
char split = 0;
for(int i = 0; i < 26 ; i++){
if(cnt[i] && cnt[i] < k){ // 如果某个字符出现的次数少于k,那么记录下该字符
split = i + 'a';
break;
}
}
//如果没有出现次数小于k的字符，那么该字符串是满足条件的子串，返回其长度
if(!split) return s.size();
//如果出现了次数小于k的字符，那么以该字符将母串分割为不同的部分，对不同的部分进行递归求母问题， 对分割的不同部分比较求出来的最长子串长度是多少。
int left = 0, right = 0;
int lgs_length = 0;
while((right = s.find(split,left)) != string::npos){
int tmp = dfs(s.substr(left,right - left),k);
if(tmp > lgs_length) lgs_length = tmp;
left = right + 1;
}
// 没有被分割的最后一部分子串，求最长子串长度
int tmp = dfs(s.substr(left,right - left),k);
if(tmp > lgs_length) lgs_length = tmp;
return lgs_length;
}
};