395. 至少有 K 个重复字符的最长子串
题目描述
输入一个字符串 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^4s只含小写英文字母1 <= k <= 10^5
解题思路：枚举种类数 + 滑动窗口
直接滑窗不行：窗口变长时“每个字符都够 k 次”这个条件既可能变好也可能变坏，不单调。办法是额外规定窗口里恰好最多有 t 种字符，t 从 1 枚举到 s 的字符种数。种类数一超过 t 就收缩 left，这样窗口的移动就单调了。每个 t 下，用 kinds 记录种类数、full 记录已达到 k 次的种类数，kinds == full 时窗口合法，更新答案。
为什么正确
对固定的 t，窗口 s[left..right] 是以 right 结尾、种类数不超过 t 的最长窗口；cnt 记录窗口内各字符次数，kinds 与 full 与 cnt 保持一致。
复杂度分析
时间 O(26·n)，即 O(Σ·n)，额外空间 O(Σ)，Σ 为字符集大小。
易错点
不能把“所有字符都够 k 次”直接当收缩条件，它没有单调性。必须固定种类数上限 t。另外 k = 1 时同一个字符会让 kinds 和 full 同时加 1，两个判断要分开写，不能用 elif。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
ans = 0
for t in range(1, len(set(s)) + 1):
cnt = collections.Counter()
left = kinds = full = 0
for right, c in enumerate(s):
cnt[c] += 1
if cnt[c] == 1:
kinds += 1
if cnt[c] == k:
full += 1
while kinds > t:
d = s[left]
if cnt[d] == k:
full -= 1
cnt[d] -= 1
if cnt[d] == 0:
kinds -= 1
left += 1
if kinds == full:
ans = max(ans, right - left + 1)
return ansclass Solution {
public int longestSubstring(String s, int k) {
int ans = 0;
int total = (int) s.chars().distinct().count();
for (int t = 1; t <= total; t++) {
int[] cnt = new int[26];
int left = 0, kinds = 0, full = 0;
for (int right = 0; right < s.length(); right++) {
int c = s.charAt(right) - 'a';
cnt[c]++;
if (cnt[c] == 1) {
kinds++;
}
if (cnt[c] == k) {
full++;
}
while (kinds > t) {
int d = s.charAt(left) - 'a';
if (cnt[d] == k) {
full--;
}
cnt[d]--;
if (cnt[d] == 0) {
kinds--;
}
left++;
}
if (kinds == full) {
ans = Math.max(ans, right - left + 1);
}
}
}
return ans;
}
}class Solution {
public:
int longestSubstring(string s, int k) {
int ans = 0;
int total = unordered_set<char>(s.begin(), s.end()).size();
for (int t = 1; t <= total; t++) {
vector<int> cnt(26, 0);
int left = 0, kinds = 0, full = 0;
for (int right = 0; right < (int)s.size(); right++) {
int c = s[right] - 'a';
cnt[c]++;
if (cnt[c] == 1) {
kinds++;
}
if (cnt[c] == k) {
full++;
}
while (kinds > t) {
int d = s[left] - 'a';
if (cnt[d] == k) {
full--;
}
cnt[d]--;
if (cnt[d] == 0) {
kinds--;
}
left++;
}
if (kinds == full) {
ans = max(ans, right - left + 1);
}
}
}
return ans;
}
};func longestSubstring(s string, k int) int {
ans := 0
seen := map[byte]bool{}
for i := 0; i < len(s); i++ {
seen[s[i]] = true
}
for t := 1; t <= len(seen); t++ {
cnt := [26]int{}
left, kinds, full := 0, 0, 0
for right := 0; right < len(s); right++ {
c := s[right] - 'a'
cnt[c]++
if cnt[c] == 1 {
kinds++
}
if cnt[c] == k {
full++
}
for kinds > t {
d := s[left] - 'a'
if cnt[d] == k {
full--
}
cnt[d]--
if cnt[d] == 0 {
kinds--
}
left++
}
if kinds == full && right-left+1 > ans {
ans = right - left + 1
}
}
}
return ans
}var longestSubstring = function(s, k) {
let ans = 0;
const total = new Set(s).size;
for (let t = 1; t <= total; t++) {
const cnt = new Array(26).fill(0);
let left = 0, kinds = 0, full = 0;
for (let right = 0; right < s.length; right++) {
const c = s.charCodeAt(right) - 97;
cnt[c]++;
if (cnt[c] === 1) {
kinds++;
}
if (cnt[c] === k) {
full++;
}
while (kinds > t) {
const d = s.charCodeAt(left) - 97;
if (cnt[d] === k) {
full--;
}
cnt[d]--;
if (cnt[d] === 0) {
kinds--;
}
left++;
}
if (kinds === full) {
ans = Math.max(ans, right - left + 1);
}
}
}
return ans;
};function longestSubstring(s: string, k: number): number {
let ans = 0;
const total = new Set(s).size;
for (let t = 1; t <= total; t++) {
const cnt = new Array<number>(26).fill(0);
let left = 0, kinds = 0, full = 0;
for (let right = 0; right < s.length; right++) {
const c = s.charCodeAt(right) - 97;
cnt[c]++;
if (cnt[c] === 1) {
kinds++;
}
if (cnt[c] === k) {
full++;
}
while (kinds > t) {
const d = s.charCodeAt(left) - 97;
if (cnt[d] === k) {
full--;
}
cnt[d]--;
if (cnt[d] === 0) {
kinds--;
}
left++;
}
if (kinds === full) {
ans = Math.max(ans, right - left + 1);
}
}
}
return ans;
}其他解法
滑动窗口通过固定字符种类数让窗口具有单调性；分治利用“出现次数不足 k 的字符一定不在答案中”来切分，两者复杂度相同。
解法 2：分治 时间 O(26n)，空间 O(26²)
统计区间内每个字符的出现次数。如果某个字符出现过但次数小于 k，任何合法子串都不能包含它。用这个字符把区间切成若干段，对每段递归求解并取最大值。所有字符次数都不小于 k 时，整个区间就是答案。
思路直接，代码短。每层递归至少去掉一种字符，所以递归深度不超过 26。最坏情况每层都要重新计数，常数比滑动窗口大。
class Solution:
def longestSubstring(self, s, k):
def dfs(l, r):
if r - l < k:
return 0
cnt = [0] * 26
for i in range(l, r):
cnt[ord(s[i]) - 97] += 1
split = -1
for c in range(26):
if 0 < cnt[c] < k:
split = c
break
if split == -1:
return r - l
res = 0
i = l
while i < r:
while i < r and ord(s[i]) - 97 == split:
i += 1
start = i
while i < r and ord(s[i]) - 97 != split:
i += 1
res = max(res, dfs(start, i))
return res
return dfs(0, len(s))class Solution {
int dfs(String s, int l, int r, int k) {
if (r - l < k) return 0;
int[] cnt = new int[26];
for (int i = l; i < r; i++) cnt[s.charAt(i) - 'a']++;
int split = -1;
for (int c = 0; c < 26; c++) {
if (cnt[c] > 0 && cnt[c] < k) { split = c; break; }
}
if (split == -1) return r - l;
int res = 0, i = l;
while (i < r) {
while (i < r && s.charAt(i) - 'a' == split) i++;
int start = i;
while (i < r && s.charAt(i) - 'a' != split) i++;
res = Math.max(res, dfs(s, start, i, k));
}
return res;
}
public int longestSubstring(String s, int k) {
return dfs(s, 0, s.length(), k);
}
}class Solution {
public:
int dfs(const string& s, int l, int r, int k) {
if (r - l < k) return 0;
vector<int> cnt(26, 0);
for (int i = l; i < r; i++) cnt[s[i] - 'a']++;
int split = -1;
for (int c = 0; c < 26; c++) {
if (cnt[c] > 0 && cnt[c] < k) { split = c; break; }
}
if (split == -1) return r - l;
int res = 0, i = l;
while (i < r) {
while (i < r && s[i] - 'a' == split) i++;
int start = i;
while (i < r && s[i] - 'a' != split) i++;
res = max(res, dfs(s, start, i, k));
}
return res;
}
int longestSubstring(string s, int k) {
return dfs(s, 0, s.size(), k);
}
};func longestSubstring(s string, k int) int {
var dfs func(l, r int) int
dfs = func(l, r int) int {
if r-l < k {
return 0
}
cnt := [26]int{}
for i := l; i < r; i++ {
cnt[s[i]-'a']++
}
split := -1
for c := 0; c < 26; c++ {
if cnt[c] > 0 && cnt[c] < k {
split = c
break
}
}
if split == -1 {
return r - l
}
res, i := 0, l
for i < r {
for i < r && int(s[i]-'a') == split {
i++
}
start := i
for i < r && int(s[i]-'a') != split {
i++
}
res = max(res, dfs(start, i))
}
return res
}
return dfs(0, len(s))
}var longestSubstring = function(s, k) {
const dfs = (l, r) => {
if (r - l < k) return 0;
const cnt = new Array(26).fill(0);
for (let i = l; i < r; i++) cnt[s.charCodeAt(i) - 97]++;
let split = -1;
for (let c = 0; c < 26; c++) {
if (cnt[c] > 0 && cnt[c] < k) { split = c; break; }
}
if (split === -1) return r - l;
let res = 0, i = l;
while (i < r) {
while (i < r && s.charCodeAt(i) - 97 === split) i++;
const start = i;
while (i < r && s.charCodeAt(i) - 97 !== split) i++;
res = Math.max(res, dfs(start, i));
}
return res;
};
return dfs(0, s.length);
};function longestSubstring(s: string, k: number): number {
const dfs = (l: number, r: number): number => {
if (r - l < k) return 0;
const cnt = new Array<number>(26).fill(0);
for (let i = l; i < r; i++) cnt[s.charCodeAt(i) - 97]++;
let split = -1;
for (let c = 0; c < 26; c++) {
if (cnt[c] > 0 && cnt[c] < k) { split = c; break; }
}
if (split === -1) return r - l;
let res = 0, i = l;
while (i < r) {
while (i < r && s.charCodeAt(i) - 97 === split) i++;
const start = i;
while (i < r && s.charCodeAt(i) - 97 !== split) i++;
res = Math.max(res, dfs(start, i));
}
return res;
};
return dfs(0, s.length);
}