# C++ AC O(nlogn)solution using divide and conquer with detailed explaination

• The idea is as follows.
Get the indexes of the character whose frequency in the string is less than k in string s, then we can narrow the range of the potential strings from the indexes we get. Finally we can solve this problem recursively.

For example,
string s : aaaaccbbcccd k = 3

indexes [6,7,11] potential strings [aaaacc, ccc]

for string : aaaacc ,
index [4] potential strings [aaaa] result = 4 in this case
for string ccc,
index [] potential strings [ccc] result = 3 in this case
Finally we get 4 :)

``````class Solution {
public:
int longestSubstring(string s, int k) {
if(s.size() < k) return 0;
if(least_times(s) >= k) return (int) s.size();
unordered_map<char,int> m; // char -> freq
int result = 0;
vector<int> indexes;
for(int i = 0;i<s.size();i++){
m[s[i]]++;
}
for(int i = 0;i<s.size();i++){
if(m[s[i]] < k) indexes.push_back(i);
}
int start = 0;
for(int i = 0; i < indexes.size();i++){
string potential = s.substr(start,indexes[i] - start);
start = indexes[i] + 1;
result = max(result, longestSubstring(potential,k));
}
string potential = s.substr(start,s.size() - start);
result = max(result, longestSubstring(potential,k));
return result;
}
int least_times(string a){ // calculate least time of a string
if(a.empty()) return 0;
unordered_map<char,int> m; // char -> freq
int r = INT_MAX;
for(int i = 0;i<a.size();i++){
m[a[i]]++;
}
for(auto iter = m.begin();iter!=m.end();++iter){
r = min(r, iter->second);
}
return r;
}
};
``````

• You using map so it's o(nlgn)but not o(n)

• This post is deleted!

• @huangweiwei unordered_map is a hash map, but by master theorem(a = b and f(n) = O(n)), this solution is O(nlogn). You are right. I have edited my title.

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