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

Categories:

题目描述
思路分析
1. 解法一：滑动窗口（推荐）
相似题目

题目描述

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

思路分析

解法一：滑动窗口（推荐）

核心思路：

使用长度为 K 的滑动窗口维护字符出现次数。

记录当前窗口中出现次数大于 1 的字符数量。

当窗口大小为 K 且重复数为 0 时计数加一。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)，字符集固定为 26。

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
}

相似题目

题目	难度	考察点
1100. 长度为 K 的无重复字符子串	中等	滑动窗口
3. 无重复字符的最长子串	中等	滑动窗口
567. 字符串的排列	中等	滑动窗口
438. 找到字符串中所有字母异位词	中等	滑动窗口
159. 至多包含两个不同字符的最长子串	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/73899351