Longest Substring With At Least K Repeating Characters Problem
Description
LeetCode Problem 395.
Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.
Example 1:
1
2
3
Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:
1
2
3
Input: s = "ababbc", k = 2
Output: 5
Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
Constraints:
- 1 <= s.length <= 10^4
- s consists of only lowercase English letters.
- 1 <= k <= 10^5
Sample C++ Code
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
class Solution {
public:
int longestSubstring(string s, int k) {
if (s.size() == 0 || k > s.size())
return 0;
if (k == 0)
return s.size();
unordered_map<char,int> Map;
for (int i = 0; i < s.size(); i++) {
Map[s[i]]++;
}
int idx =0;
while (idx <s.size() && Map[s[idx]] >= k)
idx++;
if (idx == s.size())
return s.size();
int left = longestSubstring(s.substr(0, idx), k);
int right = longestSubstring(s.substr(idx+1), k);
return max(left, right);
}
};