题目链接： https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/
题目
给你一个字符串
s和一个整数k，请你找出s中的最长子串， 要求该子串中的每一字符出现次数都不少于k。返回这一子串的长度。示例1
输入： s = “aaabb”, k = 3
输出： 3
解释： 最长子串为“aaa”，其中”a“重复了3次
示例2
输入： s = “ababbc”, k = 2
输出： 5
数据范围
1 <= s.length <= 104s仅由小写英文字母组成1 <= k <= 105
分析
没有任何思路，参照题解的分治法将此题解出，稍作记录。
首先，对于
s中的所有字符，我们可以统计它们出现的次数，对于所有出现次数小于k的字符，答案中一定不包含它。则我们只需要考虑这些字符之外的子串。我们可以遍历整个字符串，当某个字符出现次数小于
k的时候，将其位置记录下来；我们凭借这些位点，可以将原字符串s分割成许多个子串，然后按照相同的办法去处理这些子串即可。按照这样的分析，整个题目可以使用递归的写法来实现分治算法。
AC代码
class Solution {
public:
int longestSubstring(string s, int k) {
if (s.size() < k)
return 0;
// 统计频数
vector<int> cnt(26, 0);
for (auto ch : s)
cnt[ch - 'a']++;
// 记录分割位点
vector<int> split;
for (int i = 0; i < s.size(); i++)
{
if (cnt[s[i] - 'a'] < k)
{
split.push_back(i);
}
}
if (split.size() == 0) // 无需分割
return s.size();
int start = 0; // 当前子串的起点
int res = 0; // 最终答案
for (auto pos : split)
{
// string.substr(pos, len)
// 从位置pos开始的连续len个字符
res = max(res, longestSubstring(s.substr(start, pos - start), k));
start = pos + 1;
}
if (start != s.size() - 1) // 对于最后一个子串
{
res = max(res, longestSubstring(s.substr(start, s.size() - start), k));
}
return res;
}
};
参考资料
[1] 力扣官方题解.至少有K个重复字符的最长子串[EB/OL].2021-02-27
[2] 负雪明烛.借本题帮助大家理解递归[EB/OL].2021-02-27
[3] ffreturn.C++超100%的分治解法[EB/OL].2021-02-27
