LeetCode 补充题 211. 长度为 k 的无重复字符子串枚举

约 4 分钟
文章信息 2 个分类 3 个标签
分类
补充题 中等
标签
字符串 哈希表 滑动窗口

题目描述

:::fold-green 相关原题

LeetCode 原题： ✅ 1100. 长度为 K 的无重复字符子串

:::

给定小写英文字母字符串 s 和正整数 k，返回所有长度为 k 且不含重复字符的连续子串，按起点递增输出；内容相同但起点不同的窗口都保留。

示例 1：

输入： s = "abca", k = 3
输出： ["abc","bca"]

提示：

  • k >= 1
  • 允许空串。
  • k > s.length 时返回空列表。

题意分析

枚举对象是不同起点的窗口，而不是不同内容的字符串。固定长度 k 后，左右边界同步移动，用频次判断窗口内是否有重复，并按扫描顺序保留全部合法出现。

解法：固定长度滑动窗口

核心思路

[!blue]

窗口长度固定为 k，每加入右端一个字符，超过 k 时就移出左端一个字符。cnt 保存窗口内各字符的频次，dup 保存频次至少为 2 的字符种类数。

只有频次从 1 变为 2 时，才让 dup 加一；移出字符使频次从 2 变为 1 时，才让它减一。这样 dup == 0 就能常数时间判断窗口没有重复，不必每次扫描整个频次数组。

窗口已经凑满 k 个字符且 dup == 0 时，复制这个子串。按右端点递增扫描就保留了出现顺序；两个不同位置产生相同字符串时，也都要输出。

解题步骤

  1. k 超过字符串长度时直接返回空结果。
  2. 加入右端字符，频次从 1 变为 2 时增加重复字符种类数 dup。
  3. 窗口超过 k 时移出左端字符，频次从 2 变为 1 时减少 dup。
  4. 窗口恰好满 k 且 dup=0 时，复制当前子串加入结果。

代码实现

class Solution {
    public List<String> listKLenSubstrNoRepeats(String s, int k) {
        if (k > s.length()) {
            return new ArrayList<>();
        }

        int[] cnt = new int[26];
        int dup = 0;
        List<String> res = new ArrayList<>();

        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.add(s.substring(i - k + 1, i + 1));
            }
        }

        return res;
    }
}

func listKLenSubstrNoRepeats(s string, k int) []string {
    if k > len(s) {
        return []string{}
    }

    cnt := make([]int, 26)
    dup := 0
    res := []string{}

    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 = append(res, string([]byte(s[i-k+1:i+1])))
        }
    }

    return res
}

复杂度分析

  • 时间复杂度：$O(n+rk)$。
  • 空间复杂度：输出空间 $O(rk)$，额外计数空间 $O(1)$；$r$ 为结果个数。

关键点总结

[!green]

固定窗口内维护每个字符频次及重复字符种类数；窗口满且没有重复时，复制当前子串加入结果。

易错点总结

[!yellow]

  • dup 统计重复字符的种类数，不是多出的字符个数；只有跨越频次 1 与 2 的边界时才变化。
  • 先移出过期字符，再判断当前长度为 k 的窗口。
  • 内容相同但起点不同的窗口都保留，不使用集合去重。
  • 复杂度需计入子串复制，总输出字符数为 r×k。

相似题目

题目 难度 关联与区别
1100. 长度为 K 的无重复字符子串 中等 固定窗口内的重复字符判定相同；该题只统计合法窗口数量，本题需复制并返回每个合法窗口的字符串。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/24328818216
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！