# 2ms C++ recursive solution with explaination

1. First-scan: Build a local hash map to record the appearances of each character
2. Second-scan: the character which appearances smaller than k can "split" the string into many parts(it can be more than 2 parts)
3. do step 1~2 to the parts which was split in 2 recursively

Recursive exit： when all local appearances is larger than k(In an other word, the string has not been split), we get a Substring with At Least K Repeating Characters just compare them to get the longest.

class Solution {
public:
int longestSubstring(string s, int k) {
maxLen=0;
solve(s,0,s.size(),k);
return maxLen;
}
private:
int maxLen;
void solve(string &s,int left,int right,int k){
int dict[26]={0};
//count
for(int i=left;i<right;++i){
++dict[s[i]-'a'];
}
//split
int start=left;
for(int i=left;i<right;++i){
if(dict[s[i]-'a']<k){
if(start!=i){
solve(s,start,i,k);
}
start=i+1;
}
}
//check if is a legal substring
if(start==left)
maxLen=max(maxLen,right-left);
else if(start!=right)
solve(s,start,right,k);

}
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.