LeetCode 1100. 长度为 K 的无重复字符子串

2021-11-01 HGNULB 约 11 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 1100. 长度为 K 的无重复字符子串

题意分析

给定字符串 s 和整数 k，要统计 s 中长度恰好为 k 且内部字符互不相同的子串有多少个。这里的子串是连续的，所以候选一共只有 n - k + 1 个，起点从 0 到 n - k；同时题目问的是「个数」而不是「把它们列出来」，说明我们只需要一个计数器，不必保存任何子串内容。另外注意统计的是位置不同的子串，即便两个窗口的内容完全一样，只要起点不同就各算一次。

约束里给出的信号很直接。第一，长度固定为 k，这意味着窗口的宽度不会变化，不存在「为了满足条件而收缩」的情形，处理起来比变长窗口更简单。第二，字符只含小写英文字母，值域是 26，这直接决定了「有没有重复」这件事可以用一个长度 26 的计数数组表达，而且额外空间是常数级。第三，由 26 这个值域还能推出一个隐藏结论：当 k > 26 时鸽巢原理保证任何长度 k 的窗口必然有重复，答案一定是 0，虽然主逻辑天然会得出这个结果，但面试时说出来是个加分点。

边界要照顾三处：k > n 时根本凑不出任何窗口，答案是 0，必须在主循环前拦掉，否则窗口永远填不满，虽然计数逻辑不会出错但表达上容易绕；k 等于 1 时每个单字符都是合法答案，结果就是 n；整串字符互不相同时每个窗口都合法，结果是 n - k + 1。

解法：滑动窗口维护有效区间

核心思路

最朴素的做法是枚举 n - k + 1 个起点，每个起点开一个集合把 k 个字符塞进去，看集合大小是否等于 k。这是 $O(nk)$，在 n 与 k 都上万时会退化得很难看。瓶颈在哪里？相邻两个窗口重叠了 k - 1 个字符，朴素做法把这批共享的字符反复统计了 k 次，做的全是重复功。

观察到窗口从起点 i 移到 i+1 时，实际变化只有两处：右边进来一个新字符，左边出去一个旧字符。既然变化是 $O(1)$ 规模的，判定结果就应该能 $O(1)$ 地增量维护，前提是我们别把「是否有重复」这个布尔量每次从头重算，而是把它变成一个可增量更新的数值。

这个数值就是 dup：当前窗口内出现次数大于等于 2 的字符种类数。这个定义是整个解法的支点，因为它对单个字符的加入和移除都有干净的响应规则——某字符计数从 1 变 2 时，它刚刚开始重复，dup 加一；从 2 变回 1 时，它不再重复，dup 减一；其余的变化（0→1、1→0、2→3、3→2 之类）都不改变「是否重复」的状态，dup 保持不动。于是不变量可以显式写成：处理完下标 i 后，cnt 恰好记录窗口 [i-k+1, i] 内每个字符的出现次数，dup 恰好等于其中计数大于等于 2 的字符种类数，因而 dup == 0 与「该窗口无重复字符」完全等价。有了这条等价，统计就退化成扫描一遍、每步问一句 dup == 0。

解题步骤

第一步先处理 k > s.length() 直接返回 0。之所以要显式拦掉，是因为此时不存在任何长度为 k 的窗口，让主循环去跑虽然也不会数出东西，但把「无解」这个语义在入口处交代清楚，读代码的人不必再去脑内推演。

第二步准备状态：长度 26 的计数数组 cnt、重复种类数 dup、答案 res。用定长数组而非哈希表，是因为题目承诺只有小写字母，数组的随机访问常数远小于哈希，且空间是严格常数。

第三步是右端入窗。循环变量 i 表示窗口右边界，每轮先把 s[i] 计数加一，然后只在计数恰好等于 2 时让 dup++。写成「等于 2」而不是「大于等于 2」是关键：同一个字符第三次、第四次出现时它早已被计入 dup，再加就重复统计了，之后即使窗口恢复正常 dup 也归不了零。

第四步是左端出窗。当 i >= k 时，说明窗口已经超宽，最左边的 s[i-k] 必须移出：计数减一，且只在减完后恰好等于 1 时让 dup--。同样地，从 3 减到 2 时该字符仍在重复，不能提前解除标记；从 1 减到 0 时它本来就没被计入 dup，也不该减。这一步的边界条件是 i >= k 而不是 i >= k - 1，因为下标 i 时窗口自然覆盖 [i-k+1, i]，只有当 i-k 还是个合法下标（即 i >= k）时才有旧字符需要吐出。

第五步是统计。i >= k - 1 表示窗口首次被填满，从这一刻起每个 i 都对应一个完整窗口，此时若 dup == 0 就把 res 加一。判定必须放在入窗和出窗之后，因为只有两步都做完，cnt 与 dup 才真正描述当前这个宽度为 k 的窗口。循环结束返回 res。

以 s = "abcabc"、k = 3 走一遍。i=0 字符 a，cnt[a]=1，未触发 dup；i >= 3 不成立不出窗；i >= 2 不成立不统计。i=1 字符 b，cnt[b]=1；同样两个条件都不满足。i=2 字符 c，cnt[c]=1，dup 仍是 0；i >= 3 不成立；i >= 2 成立且 dup == 0，窗口 "abc" 合法，res=1。i=3 字符 a，cnt[a] 变成 2，触发 dup=1；此时 i >= 3 成立，移出 s[0]= a，cnt[a] 减回 1，恰好等于 1 于是 dup=0——这一加一减正是「同一个字符滑出又滑入」的典型场景，若少写任何一边 dup 都会卡在 1 上；随后 dup == 0，窗口 "bca" 合法，res=2。i=4 字符 b 同理，cnt[b] 到 2 使 dup=1，移出 s[1]= b 使 dup=0，窗口 "cab" 合法，res=3。i=5 字符 c 同理，窗口 "abc" 合法，res=4。循环结束返回 4，与手工枚举 "abc"、"bca"、"cab"、"abc" 四个窗口一致。

代码实现

class Solution {
    // 记录当前窗口中出现次数大于 1 的字符数量。
    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 {
    // 记录当前窗口中出现次数大于 1 的字符数量。
    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)$，其中 n 表示字符串长度。每个下标只作为右端进窗一次、作为左端出窗一次，两次都是 $O(1)$ 的数组读写，判定 dup == 0 也是常数时间，全程没有任何嵌套扫描。

空间复杂度：$O(1)$，只有一个长度 26 的计数数组和三个整型变量，与输入规模无关；即便把字符集换成 ASCII 也只是把 26 换成 128，仍是常数。

关键点总结

把「窗口是否合法」压缩成一个可增量维护的标量，是定长窗口题的通用降维手法。这里的 dup 是重复字符种类数，别的题里可能是「不同字符个数」「未满足的目标字符数」，形式不同但套路一致：找一个对单点增删有 $O(1)$ 响应规则的量。

更新触发条件必须写成「恰好等于阈值」而不是「跨过阈值」。加的时候只在 cnt == 2 时动，减的时候只在 cnt == 1 时动，这样每个字符的重复状态在整个生命周期里被恰好标记一次、撤销一次，计数才不会漂移。

定长窗口不需要 while 收缩循环，一个 if 就够了。区分「定长」与「变长」是面试时的第一个判断：变长窗口要用 while 一直收缩到合法，定长窗口每步吐出恰好一个元素，两者的代码骨架完全不同，混用是常见的丢分点。

字符集有界时优先用定长数组做计数，比哈希表快且空间可控。面试官若把字符集放宽到 Unicode，再换成哈希表即可，其余逻辑一行不改，这个「可替换性」值得主动提一句。

注意到 k > 26 必然无解，可以在开头加一条剪枝。这不是必需的优化，但能体现你把值域约束和鸽巢原理联系起来了，是面试里成本极低的展示机会。

统计时机固定在「入窗和出窗都完成之后」。任何时候只要状态更新和答案读取的顺序错开，不变量就不再成立，这条原则在所有滑动窗口题里都适用。

易错点总结

错误写法：dup++ 的条件写成 if (cnt[idx] >= 2)。用例 s = "aaa"、k = 2 → 第三个 a 又让 dup 加一变成 2，之后左端移出把它减到 1，dup 永远回不到 0，本该为 0 的答案还是 0 看不出来，但换 s = "aaab"、k = 2 时窗口 "ab" 也被判为有重复，返回 0 而非 1。

错误写法：dup-- 的条件写成 if (cnt[leftIdx] >= 1)。用例 s = "aab"、k = 2 → 移出第一个 a 时 cnt[a] 从 2 减到 1 触发一次减，移出第二个 a 时从 1 减到 0 又触发一次减，dup 变成 -1，后续窗口的合法性判断彻底失真。

错误写法：出窗条件写成 if (i >= k - 1)。用例 s = "abc"、k = 3 → i=2 时就去访问 s[-1]，Java 抛 StringIndexOutOfBoundsException，Go 直接 panic。

错误写法：统计条件写成 if (i >= k && dup == 0)。用例 s = "abc"、k = 3 → 唯一的合法窗口出现在 i=2，条件要求 i≥3 永远不成立，返回 0 而非 1，第一个窗口被整体漏掉。

错误写法：把统计放在入窗之后、出窗之前。用例 s = "abca"、k = 3 → i=3 时窗口内容其实是 4 个字符 "abca"，dup 因第二个 a 而为 1，判定失败，但正确窗口 "bca" 是合法的，返回 1 而非 2。

错误写法：漏掉 k > s.length() 的返回，且把统计条件误写成 i >= 0。用例 s = "ab"、k = 5 → 每个未填满的短窗口都被当作合法答案计入，返回 2 而非 0。

错误写法：用 HashSet 判重，每轮把窗口 k 个字符重新塞一遍。用例 s 长度 2 万且 k = 10000 → 逻辑正确但复杂度退化到 $O(nk)$，两亿次操作直接超时。

错误写法：Go 里写成 idx := s[i] - 'a' 之后又用 cnt[s[i]]++。用例任意含 'z' 的串 → s[i] 是 122 这个 byte 值，越过长度 26 的切片边界，panic: index out of range。

错误写法：认为内容相同的窗口只算一次，于是把合法子串塞进 Set 去重后取 size。用例 s = "abcabc"、k = 3 → "abc" 出现两次被去重，返回 3 而非 4。

错误写法：忘记在移出时对 cnt 做减法，只减了 dup。用例 s = "abcd"、k = 2 → 计数只增不减，i=3 时 cnt 描述的是整个前缀而非窗口，dup 与 cnt 失去对应，后续判定随输入长度越错越离谱。

相似题目

题目	难度	考察点
3. 无重复字符的最长子串	中等	同样判重，但窗口长度可变，求最长而非计数，需 while 收缩
438. 找到字符串中所有字母异位词	中等	定长窗口比对的是「计数是否完全匹配」，用 diff 计数替代 dup
1456. 定长子串中元音的最大数目	中等	维护的标量是元音个数，求最大值而非合法计数，骨架完全一致
643. 子数组最大平均数 I	简单	定长窗口的最简形态，标量就是窗口和，可作为本题的入门参照
340. 至多包含 K 个不同字符的最长子串	中等	k 约束的是字符种类数而非窗口长度，窗口因此变长
159. 至多包含两个不同字符的最长子串	中等	上一题固定 k=2 的特例，可用两个变量代替计数表
424. 替换后的最长重复字符	中等	合法判据是「窗口长减最高频次不超过 k」，最高频次只增不减是难点
904. 水果成篮	中等	值域不再是 26 个字母，必须用哈希表，且需在收缩时清理零计数键
992. K 个不同整数的子数组	困难	「恰好 K 个」要用「至多 K 个减至多 K-1 个」的差分技巧转化
76. 最小覆盖子串	困难	判据从「无重复」变成「覆盖目标」，需要两张计数表加满足数计量
1343. 大小为 K 且平均值大于等于阈值的子数组数目	中等	同为定长窗口计数题，把阈值比较改写成整数乘法可避免精度问题