【滑动窗口】至少有k个重复字符的最长子串
前言
编程语言： Java/go实现
滑动窗口的一道标注medium：no -> 实际hard的题， 本题题解还能用滑动窗口解是我没想到的。
本题应用滑动窗口的条件是通过题目给定限制猜解法， 然后枚举常数次行为来控制变量， 进而构建了单调性的条件， 应用了滑动窗口。
没有单调性转化构建处单调性， 子串问题是连续的， 故而应用了滑动窗口这个技巧。
题目：395. 至少有 K 个重复字符的最长子串
给定一个字符串
s和一个整数k，找出s中长度最长的子串，要求子串中的每个字符出现的次数均不小于k。如果不存在这样的子串，则返回 0。
思路：滑动窗口解法
因为蒟蒻，不太会动态规划，分治递归也没看题解。滑动窗口写了一份代码。求轻喷……我是菜鸟呜呜呜……
解题思路
这道题既要控制字符种类，又要保证每个子串中的每个字符出现次数大于等于 k。
一看就是 Hard 题披着 中等 的衣服……
不过题目范围给定了 s 仅由小写英文字母组成，因此可以按照字符种类（‘a’ -> ‘z’）穷举，相当于控制变量法。
- 一个种类的字符子串求一个最长长度结果。
- 两个种类字符的子串求一个最长长度结果。
- ……以此类推，直至求出 26 种字符的结果。
然后依次 PK，最终得到整个函数的返回值。
为什么联想到滑动窗口呢？
求解子数组或者子串的最长长度，根据经验可以联想到滑动窗口的解法。
其实是单调性分析出来的。
以示例 2 为例分析
示例 2：
输入：s = "ababbc", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
分析步骤
- 一种字符的情况：
满足一种字符且该字符大于等于k=2次，字符串"bb"符合，长度为2。 - 两种字符的情况：
满足两种字符且两个字符大于等于2次，子串"ababb"符合，长度为5。 - 三种字符的情况：
满足三种字符且三个字符大于等于2次，没有子串符合，因为'c'至多出现一次，没有一个正确的结构，不参与比较。 - 枚举结束：
将 3 种情况的结果进行 PK，决出最大的子串长度5。
核心思想总结
- 说明：当子串包含两种字符
a和b时，它们满足>=k的条件，且子串长度最长。 - 具体实现：题目要求子串满足字符种类和每个字符
>=k两种复合条件处理，因此以滑动窗口结合字符种类穷举即可。
解题过程
题目函数如下：
class Solution {
public int longestSubstring(String s, int k) {
}
}
以下是我的 Java 代码实现：
代码实现
首先搞一个哈希表。由于只有小写字母，因此开一个长度为 26 的数组空间。利用 字符-'a' 将小写字母的 ASCII 值映射到 0, 1, 2, ... 25。
比如：
'a': 97 - 'a' => 0下标处。'z': 'z' - 'a' => 25。
相信大佬们都会。这个数组哈希表主要是统计字符串中字母的种类数。
int[] hash = new int[26];
int cnt; // 记录字符种类数
既然要统计字符种类，为什么不用布尔数组呢？
答案：因为下面还要复用这个 hash 数组。
实现滑动窗口
1. 外层循环
cnt 是总的字符种类数，要从 1 种字符种类枚举到 cnt 种类型，因此需要写个外层循环。
2. 内层滑动窗口
复用 hash 数组：
key：字符种类。value：该字符出现的次数。
定义 type 为字符类型数，从 1 -> cnt。
3. 核心过程
滑动窗口具体操作如下：
- 定义
l, r = 0, 0为滑动窗口的同向双指针。 - 定义
kinds和satisfy：kinds是当前窗口的字符种类数。satisfy是当前窗口内满足条件（即字符个数>=k）的字符数。
- 初始化
hash数组和上述变量。
窗口扩展
-
右指针扩展：
- 将
r位置的字符映射到哈希表的位置，使其自增 1。 - 如果该字符是第一次出现在窗口内（
hash[index] == 1），种类数kinds++。 - 如果当前字符满足个数
>=k，则满足条件的字符数satisfy++。
- 将
-
左指针收缩：
- 如果当前
kinds大于此时枚举字符数type，开始循环挪动左指针。 - 如果
hash[index2]数量由1 -> 0，说明该字符被移除，kinds--。 - 如果数量是
k -> k-1，满足条件的字符数satisfy--。 - 循环逻辑直至
kinds == type。
- 如果当前
合法窗口更新答案
字符的种类数已经符合要求，查看满足要求的字符数是否等于 type：
如果满足条件，则结算：
ans = Math.max(ans, r - l + 1);
最终返回答案 ans。
复杂度分析
-
时间复杂度：
( O ( n ) ) (O(n)) (O(n))，因为外层循环最多 O ( c n t ) O(cnt) O(cnt)，内层循环为滑动窗口 O ( n ) O(n) O(n)。cnt最多是 26，因此 O ( 26 ) × O ( n ) = O ( n ) O(26) \times O(n) = O(n) O(26)×O(n)=O(n)。 -
空间复杂度：
O ( 1 ) O(1) O(1)，仅仅用了几个变量，以及一个固定长度的int[26]数组作哈希表。
Java 代码
以下是完整代码：
class Solution {
public int longestSubstring(String s, int k) {
int n = s.length();
int ans = 0;
for (int type = 1; type <= 26; type++) {
int[] hash = new int[26];
int l = 0, r = 0, kinds = 0, satisfy = 0;
while (r < n) {
int indexR = s.charAt(r) - 'a';
hash[indexR]++;
if (hash[indexR] == 1) kinds++;
if (hash[indexR] == k) satisfy++;
while (kinds > type) {
int indexL = s.charAt(l) - 'a';
if (hash[indexL] == k) satisfy--;
if (hash[indexL] == 1) kinds--;
hash[indexL]--;
l++;
}
if (kinds == type && kinds == satisfy) {
ans = Math.max(ans, r - l + 1);
}
r++;
}
}
return ans;
}
}
Go代码
func longestSubstring(s string, k int) int {
var hash [26]int
cnt := 0
for _,ch := range s{
if hash[ch-'a']==0{
cnt += 1
}
hash[ch-'a']=1
}
ans := 0
for i:=1;i<=cnt;i++{
memeset_hash(&hash)
var l,r,kinds,satisfy int
for r<len(s){
index := s[r] - 'a'
hash[index] += 1
if hash[index] == 1 {
kinds += 1
}
if hash[index] == k {
satisfy += 1
}
for kinds > i{
index2 := s[l] - 'a'
hash[index2] -= 1
if hash[index2] == 0{
kinds -= 1
}
if hash[index2] == k-1{
satisfy -= 1
}
l += 1
}
if satisfy == i{
ans = max(ans, r - l + 1)
}
r += 1
}
}
return ans
}
func memeset_hash(hash *[26]int){
for i := range hash{
hash[i]=0
}
}
func max(x, y int) int{
if x > y{
return x
}
return y
}
总结
通过数据范围进行常数次枚举， 构造单调性，然后结合子串问题应用了滑动窗口的技巧。
本题还有动态规划和分治递归的热门解法， 读者可以查看一下leetcode的相关题解。
希望对您有帮助，😉😉😉…