Longest Substring with At Least K Repeating Characters

Desicription

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

1
2
3
4
5
6
7
Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

1
2
3
4
5
6
7
Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int longestSubstring(const std::string& s, const int& k) {
return longestSubstring(s, k, 0, static_cast<int>(s.size()) - 1);
}

int longestSubstring(const std::string& s, const int& k, int left, int right) {
if(left > right) {
return 0;
}

auto count = std::vector<int>(26, 0);
for(int i = left; i <= right; i++) {
count[s[i] - 'a']++;
}

int res = right - left + 1;
for(int i = left; i <= right; i++) {
if(count[s[i] - 'a'] > 0 && count[s[i] - 'a'] < k) {
res = std::max(longestSubstring(s, k, left, i - 1), longestSubstring(s, k, i + 1, right));
return res;
}
}
return res;
}
};