# C++, O(n), Divide and Conquer

• In every step of DC, at least 1 character, let's say, 'a', is chosen to divide the string, then all substrings in following recursive calls have no 'a'. The level of DC is at most 26, otherwise you run out of character to divide, and each level is O(n). The run time is 3 ms.

``````class Solution {
public:
int longestSubstring(string s, int k) {
int n = s.size();
return helper(s, 0, n-1, k);
}
private:
// looking for longest string within index range [l, r]
int helper(string& s, int l, int r, int k) {
vector<int> mp(26, 0);
for (int i = l; i <= r; i++) mp[s[i]-'a']++;
// check whether the whole string meets requirement
bool pass = true;
for (int i = 0; i < 26 && pass; i++) {
if (mp[i] && mp[i] < k)
pass = false;
}
if (pass) return r-l+1;
// using all characters with occurrence > 0 && < k to divide the string
int i = l, ans = 0;
for (int j = l; j <= r; j++) {
if (mp[s[j]-'a'] && mp[s[j]-'a'] < k) {
ans = max(ans, helper(s, i, j-1, k));
i = j+1;
}
}
return max(ans, helper(s, i, r, k));
}
};
``````

• Hi zestypanda,

I found the same solution and implemented it. But after that I couldn't prove that it is O(n).

``````The level of DC is at most 26, otherwise you run out of character to divide, and each level is O(n).
``````

This sentences clearly explain why it is O(n). Thanks!

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