leetcode 395. Longest Substring with At Least K Repeating Characters

时间:2023-03-08 22:34:27

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:

Input:
s = "aaabb", k = 3 Output:
3 The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2 Output:
5 The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

这个题目挺不错了。

主要还是统计出现次数没有达到k的字母作为分界点,我写的递归类似线段树,一开始超时了,我也没搞清楚为什么,后来调试的时候发现for循环的时候重复计算了,加个return就过了。

笨拙的代码

class Solution {
public:
int ans = ;
map<char,int> mp;
void dfs(int l, int r, int k, string &s) {
if (l > r || r - l + < k) return ;
int mark = ;
mp.clear();
for (int i = l; i <= r; ++i) mp[s[i]]++;
for (int i = l; i <= r; ++i) {
if(mp[s[i]] < k) {
dfs(l, i - , k, s);
dfs(i + , r, k, s);
return ;
mark = ;
}
}
if (!mark) {
ans = max(r - l + , ans);
}
}
int longestSubstring(string s, int k) {
int n = s.length();
dfs(, n - , k, s);
return ans;
}
};