# 3ms C++ solution by Divide&Conquer

• ``````#include <iostream>
#include <vector>
class Solution {
public:
int longestSubstring(std::string s, int k) {
return findMax(s,k,0,s.size()-1);
}
int findMax(const std::string& s,int k, int start,int end){
if (end-start+1<k){
return 0;
}
if (k==0||k==1) return end-start+1;
std::vector<int> char_vec(26,0);
for (int i=start;i<=end;++i){
char_vec.at(int(s[i]-'a'))++;
}
bool satisfied = true;
for (int i=start;i<=end;i++){
if(char_vec.at(s[i]-'a')< k) {
satisfied = false;
break;
}
}
//check if the whole string meets the requirement
if (satisfied) return end-start+1;
//separate the whole string into multiple substrings;
// the delimiter are the chars with count <k
// find max length recursively on the substrings.
int max =0;
int left=0;
int right=0;
for (int i=start;i<=end;i++){
if(char_vec.at(s[i]-'a')<k){
continue;
}
left =i;//substring starting point
right=i;//substring ending point
while(right<=end&&char_vec.at(s[right]-'a')>=k){
right++;
}
if (right>end){
max = std::max(max,findMax(s,k,left,end));
break;
}
max = std::max(max,findMax(s,k,left,right-1));
i = right;
}
return max;
}
};
``````

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