当前位置：首页 > ai >正文

LeetCode 395.至少有K个重复字符的最长子串

ai 2025/7/21 6:11:38

给你一个字符串 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$
s 仅由小写英文字母组成
1 <= k <= 10 $^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次的字符splitchar 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$ )，因为递归深度最大为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'];// 如果窗口内该字符数还不足kif (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'];// 如果该字符数量减为0if (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;}
};