# C++ O(n^2) solution

• ``````class Solution {
public:
int getLength(string s, int k) {
int chars[26] = { 0, };
for (int i = 0; i < s.length(); i++)
chars[s[i] - 'a']++;

vector<int> nums(s.length(), 0);
for (int i = 0; i < s.length(); i++)
nums[i] = chars[s[i] - 'a'];

int result = 0;
int res = 0;
for (int i = 0; i < s.length(); i++) {
if (nums[i] >= k) {
res++;
result = max(res, result);
}
else
res = 0;
}

return result;
}

int longestSubstring(string s, int k) {
int result = 0;
int chars[26] = { 0, };
for (int i = 0; i < s.length(); i++)
chars[s[i] - 'a']++;

unordered_set<char> uset;
for (int i = 0; i < 26; i++) {
if (chars[i] < k && chars[i] > 0)
uset.insert(i + 'a');
}

if (uset.empty())
return s.length();

string t = "";
for (int i = 0; i < s.length(); i++) {
if (uset.count(s[i]) > 0) {
if (t != "") {
result = max(result, getLength(t, k));
t = "";
}
}
else {
t += string(1, s[i]);
}
}

if(t.length() > k) {
result = max(result, getLength(t, k));
}

return result;
}
};
``````

• copy-pasted your code on OJ, and get wrong answer on this test case:
"ababacb"
3

1
Expected:
0

• You're right. Thank you for pointing out my mistake. I revised my solution and it works well with the test cases.

``````class Solution {
public:
int longestSubstring(string s, int k) {
if (s.length() < k)
return 0;

int result = s.length();
int chars[26] = { 0, };
for (int i = 0; i < s.length(); i++)
chars[s[i] - 'a']++;

int i = 0;
while (i < s.length() && chars[s[i] - 'a'] >= k)
i++;

if (i == s.length())
return s.length();

return max(longestSubstring(s.substr(0, i), k), longestSubstring(s.substr(i + 1), k));
}
};
``````

• @jaewoo Can you explain why this is O(n)?

• @leogogogo After revised my first code, the complexity now is O(n^2). Thank you for your comment and I changed the title.

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