LeetCode 1100. 长度为 K 的无重复字符子串
题目描述
题意分析
统计长度恰好为
k、且内部字符互不重复的连续子串数量。不同起点对应不同子串位置，即使内容相同也要分别计数。题目只包含小写英文字母。相邻的定长子串仅相差一个移出的左端字符和一个移入的右端字符，因此不用每次重新检查全部
k个字符。维护窗口内的字符频次，再记录当前有多少种字符发生重复，就能在每次滑动后直接判断。
解法：滑动窗口维护有效区间
核心思路
[!blue]
cnt[c]表示字母c在当前窗口中的次数，dup表示频次至少为二的字母种类数，res累计合法窗口数。dup == 0当且仅当窗口没有重复字符。扫描右端
i时先加入s[i]：只有频次从一变二，才出现一种新的重复字母，需要增加dup；从二变三等变化仍是同一种重复，不再增加。若i >= k，再移除旧左端s[i-k]；只有频次从二变一，才解除一种重复，需要减少dup。加入和移除完成后，计数对应的区间恰好是
[max(0, i-k+1), i]。当i >= k-1时它才达到长度k，此时若dup == 0，将res加一。每个定长子串都有唯一的右端，所以扫描恰好检查所有候选一次，不会遗漏或重复计数。窗口本身可以暂时含有重复字符，移动边界只为维持固定长度；是否计入答案由
dup决定。k大于字符串长度时没有完整窗口，入口直接返回零。
解题步骤
- 加入右端并按阈值更新 dup。
- 长度超过 k 时移出旧左端。
- 窗口满 k 位后判断并计数。
代码实现
class Solution {
public int numKLenSubstrNoRepeats(String s, int k) {
if (k > s.length()) {
return 0;
}
int[] cnt = new int[26];
int dup = 0;
int res = 0;
for (int i = 0; i < s.length(); i++) {
int idx = s.charAt(i) - 'a';
cnt[idx]++;
// 只有从一份变两份，才新增一个重复种类。
if (cnt[idx] == 2) {
dup++;
}
if (i >= k) {
int leftIdx = s.charAt(i - k) - 'a';
cnt[leftIdx]--;
// 只有从两份降一份，才解除这一种重复。
if (cnt[leftIdx] == 1) {
dup--;
}
}
// 窗口已满且更新完成后才计数。
if (i >= k - 1 && dup == 0) {
res++;
}
}
return res;
}
}
func numKLenSubstrNoRepeats(s string, k int) int {
if k > len(s) {
return 0
}
cnt := make([]int, 26)
dup := 0
res := 0
for i := 0; i < len(s); i++ {
idx := s[i] - 'a'
cnt[idx]++
// 只有从一份变两份，才新增一个重复种类。
if cnt[idx] == 2 {
dup++
}
if i >= k {
leftIdx := s[i-k] - 'a'
cnt[leftIdx]--
// 只有从两份降一份，才解除这一种重复。
if cnt[leftIdx] == 1 {
dup--
}
}
// 窗口已满且更新完成后才计数。
if i >= k-1 && dup == 0 {
res++
}
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$。每个字符入窗一次、至多出窗一次，每次只更新两个频次和重复种类数。
- 空间复杂度：$O(1)$，频次数组固定为 26 个位置。
关键点总结
[!green]
- dup 数的是重复的字符种类，不是多余字符总个数。
- 第一次计数在右端下标 k−1，第一次移除在 k。
易错点总结
[!yellow]
- 加入第三个相同字母又增加 dup，会重复记录同一种。
- 从三减到二就解除重复，会把仍含重复的窗口算入。
- 入窗后、出窗前就判断，会使用临时 k+1 长度窗口。
k == 1时每个单字符窗口都合法；k > 26时任何完整窗口都会重复，当前判断自然得到零。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 3. 无重复字符的最长子串 | 中等 | 原题求任意长度的最长无重复子串，本题窗口长度固定，只统计合法窗口数量。 |
| 438. 找到字符串中所有字母异位词 | 中等 | 同样对定长窗口维护字符频次，本题要求全部次数不超过1，原题要求与模式频次一致。 |
| 补充题 211. 长度为 k 的无重复字符子串枚举 | 中等 | 都维护长度为 k 的滑动窗口和字符频次；补充题返回全部符合条件的窗口。 |
| 159. 至多包含两个不同字符的最长子串 | 中等 | 用滑动窗口维护字符频次和有效左边界；本题固定窗口长度后统计无重复窗口，该题允许最多两种字符。 |
| 340. 至多包含 K 个不同字符的最长子串 | 中等 | 用滑动窗口维护字符频次和有效左边界；本题固定窗口长度后统计无重复窗口，该题允许最多 k 种字符。 |
| 904. 水果成篮 | 中等 | 用滑动窗口维护字符频次和有效左边界；本题固定窗口长度后统计无重复窗口，该题把两种水果限制转为两类元素窗口。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！