给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
如果不存在这样的子字符串，则返回 0。
示例 1：
输入：s = “aaabb”, k = 3
输出：3
解释：最长子串为 “aaa” ，其中 ‘a’ 重复了 3 次。
示例 2：
输入：s = “ababbc”, k = 2
输出：5
解释：最长子串为 “ababb” ，其中 ‘a’ 重复了 2 次， ‘b’ 重复了 3 次。
提示：
1 <= s.length <= 10 4 ^4 4
s 仅由小写英文字母组成
1 <= k <= 10 5 ^5 5
法一：由于子串中至少需要K个重复字符，因此我们可以遍历一下输入字符串s，看s中哪个字符不足K个，包含该字符的子串一定不符合题目要求，因此该字符就把s分隔为了多个部分，因此可以对这些部分再次重复以上操作：
class Solution {
public:
int longestSubstring(string s, int k) {
return dfs(s, 0, s.size() - 1, k);
}
private:
int dfs(const string &s, int l, int r, int k) {
// 统计l到r闭区间每个字符的出现次数
vector<int> cnt(26, 0);
for (int i = l; i <= r; ++i) {
++cnt[s[i] - 'a'];
}
// 找到一个出现次数小于k次的字符split
char split = '\0';
for (int i = 0; i < 26; ++i) {
if (cnt[i] > 0 && cnt[i] < k) {
split = i + 'a';
break;
}
}
// 如果所有字符出现次数都大于等于k，直接返回本次迭代的子串长度即可
if (split == '\0') {
return r - l + 1;
}
int ret = 0;
while (l <= r) {
// 找到第一个非split的字符
while (l <= r && s[l] == split) {
++l;
}
if (l > r) {
break;
}
// 找到下一个split字符
int start = l;
while (l <= r && s[l] != split) {
++l;
}
// 对两个split字符之间的子串进行递归
ret = max(ret, dfs(s, start, l - 1, k));
}
return ret;
}
};
如果字符串s的长度为n，则此算法时间复杂度为O(26*n)，因为每层递归都会去除某种字符，而字符种类为26；空间复杂度为O(26 2 ^2 2)，因为递归深度最大为26，且每层递归需要26的cnt空间。
法二：滑动窗口。我们可以规定子串中只含有x种字符，x取值为1到26，循环26次。每次循环中进行滑窗，滑窗时需要维护：
1.字符种类数等于当前x。
2.当前窗口内，同种字符不足K个的字符数。
当字符种类数为x，且同种字符不足K个的字符数为0时，即为一个符合题意的子串：
class Solution {
public:
int longestSubstring(string s, int k) {
int ans = 0;
for (int i = 1; i <= 26; ++i) {
// 记录每种字符的数量
vector<int> cnt(26, 0);
int left = 0;
// 字符种类数
int charKindNum = 0;
// 同种字符不足K个的字符数
int unsatisfiedCharNum = 0;
for (int j = 0; j < s.size(); ++j) {
// 如果当前窗口内没有此字符
if (cnt[s[j] - 'a'] == 0) {
// 增加字符种类数
++charKindNum;
}
// 增加窗口内该字符的数量
++cnt[s[j] - 'a'];
// 如果窗口内该字符数还不足k
if (cnt[s[j] - 'a'] < k) {
// 增加同种字符不足K个的字符数
++unsatisfiedCharNum;
// 如果窗口内该字符正好满足k个
} else if (cnt[s[j] - 'a'] == k) {
// 减少同种字符不足K个的字符数
unsatisfiedCharNum -= k - 1;
}
// 如果字符种类数超出i，需要右移左窗口
while (charKindNum > i) {
// 减少窗口内该字符的数量
--cnt[s[left] - 'a'];
// 如果该字符数量减为0
if (cnt[s[left] - 'a'] == 0) {
// 减少字符种类数
--charKindNum;
}
// 如果减少该字符后，正好不满足k个了
if (cnt[s[left] - 'a'] == k - 1) {
// 增加窗口内同种字符不足K个的字符数
unsatisfiedCharNum += k - 1;
// 如果减少该字符前，该字符已经不满足k个
} else if (cnt[s[left] - 'a'] < k - 1) {
// 窗口内同种字符不足K个的字符数减1
--unsatisfiedCharNum;
}
// 右移左窗口
++left;
}
// 如果窗口内同种字符不足K个的字符数为0，即全部至少有K个字符时
if (unsatisfiedCharNum == 0) {
ans = max(ans, j - left + 1);
}
}
}
return ans;
}
};
如果字符串s的长度为n，则此算法时间复杂度为O(26*(n + 26))，因为循环了26次，每次循环中需要初始化长为26的cnt数组，以及遍历s；此算法空间复杂度为O(26)。