LeetCode 1100: Find K-Length Substrings With No Repeated Characters (Sliding Window + Frequency)
LeetCode 1100Sliding WindowStringToday we solve LeetCode 1100 - Find K-Length Substrings With No Repeated Characters.
Source: https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/
English
Problem Summary
Given a string s and integer k, count substrings of length k that contain no repeated characters.
Key Insight
Use a fixed-size sliding window and track character frequencies. A window is valid when its size is exactly k and no character appears more than once.
Algorithm
- Move right pointer and add current character.
- If a character count becomes 2, shrink from left until it returns to 1.
- If window size exceeds k, remove leftmost character.
- When window size equals k, count one valid substring.
Complexity Analysis
Each character enters and leaves the window at most once.
Time: O(n).
Space: O(1) for lowercase letters (or O(Σ) for charset size).
Common Pitfalls
- Forgetting to shrink when duplicates appear.
- Not maintaining window length at most k.
- Counting windows before size reaches k.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int numKLenSubstrNoRepeats(String s, int k) {
if (k > s.length()) return 0;
int[] cnt = new int[26];
int left = 0, ans = 0;
for (int right = 0; right < s.length(); right++) {
int r = s.charAt(right) - 'a';
cnt[r]++;
while (cnt[r] > 1) {
cnt[s.charAt(left) - 'a']--;
left++;
}
while (right - left + 1 > k) {
cnt[s.charAt(left) - 'a']--;
left++;
}
if (right - left + 1 == k) {
ans++;
}
}
return ans;
}
}func numKLenSubstrNoRepeats(s string, k int) int {
if k > len(s) {
return 0
}
cnt := make([]int, 26)
left, ans := 0, 0
for right := 0; right < len(s); right++ {
r := int(s[right] - 'a')
cnt[r]++
for cnt[r] > 1 {
cnt[int(s[left]-'a')]--
left++
}
for right-left+1 > k {
cnt[int(s[left]-'a')]--
left++
}
if right-left+1 == k {
ans++
}
}
return ans
}class Solution {
public:
int numKLenSubstrNoRepeats(string s, int k) {
if (k > (int)s.size()) return 0;
vector<int> cnt(26, 0);
int left = 0, ans = 0;
for (int right = 0; right < (int)s.size(); right++) {
int r = s[right] - 'a';
cnt[r]++;
while (cnt[r] > 1) {
cnt[s[left] - 'a']--;
left++;
}
while (right - left + 1 > k) {
cnt[s[left] - 'a']--;
left++;
}
if (right - left + 1 == k) ans++;
}
return ans;
}
};class Solution:
def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
if k > len(s):
return 0
cnt = [0] * 26
left = 0
ans = 0
for right, ch in enumerate(s):
r = ord(ch) - ord('a')
cnt[r] += 1
while cnt[r] > 1:
cnt[ord(s[left]) - ord('a')] -= 1
left += 1
while right - left + 1 > k:
cnt[ord(s[left]) - ord('a')] -= 1
left += 1
if right - left + 1 == k:
ans += 1
return ans/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var numKLenSubstrNoRepeats = function(s, k) {
if (k > s.length) return 0;
const cnt = new Array(26).fill(0);
let left = 0;
let ans = 0;
for (let right = 0; right < s.length; right++) {
const r = s.charCodeAt(right) - 97;
cnt[r]++;
while (cnt[r] > 1) {
cnt[s.charCodeAt(left) - 97]--;
left++;
}
while (right - left + 1 > k) {
cnt[s.charCodeAt(left) - 97]--;
left++;
}
if (right - left + 1 === k) {
ans++;
}
}
return ans;
};中文
题目概述
给定字符串 s 和整数 k，统计长度恰好为 k 且没有重复字符的子串数量。
核心思路
用固定长度滑动窗口，并维护窗口内字符频次。窗口长度为 k 且所有字符频次都不超过 1 时，就是一个合法答案。
算法步骤
- 右指针右移并加入新字符。
- 若某字符频次变成 2，左指针右移直到该字符频次回到 1。
- 若窗口长度超过 k，持续移除左端字符。
- 当窗口长度等于 k 时，答案加一。
复杂度分析
每个字符最多进窗口一次、出窗口一次。
时间复杂度：O(n)。
空间复杂度：小写字母场景为 O(1)，一般字符集为 O(Σ)。
常见陷阱
- 出现重复字符后没有及时收缩窗口。
- 没有限制窗口长度不超过 k。
- 窗口长度不足 k 时提前计数。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int numKLenSubstrNoRepeats(String s, int k) {
if (k > s.length()) return 0;
int[] cnt = new int[26];
int left = 0, ans = 0;
for (int right = 0; right < s.length(); right++) {
int r = s.charAt(right) - 'a';
cnt[r]++;
while (cnt[r] > 1) {
cnt[s.charAt(left) - 'a']--;
left++;
}
while (right - left + 1 > k) {
cnt[s.charAt(left) - 'a']--;
left++;
}
if (right - left + 1 == k) {
ans++;
}
}
return ans;
}
}func numKLenSubstrNoRepeats(s string, k int) int {
if k > len(s) {
return 0
}
cnt := make([]int, 26)
left, ans := 0, 0
for right := 0; right < len(s); right++ {
r := int(s[right] - 'a')
cnt[r]++
for cnt[r] > 1 {
cnt[int(s[left]-'a')]--
left++
}
for right-left+1 > k {
cnt[int(s[left]-'a')]--
left++
}
if right-left+1 == k {
ans++
}
}
return ans
}class Solution {
public:
int numKLenSubstrNoRepeats(string s, int k) {
if (k > (int)s.size()) return 0;
vector<int> cnt(26, 0);
int left = 0, ans = 0;
for (int right = 0; right < (int)s.size(); right++) {
int r = s[right] - 'a';
cnt[r]++;
while (cnt[r] > 1) {
cnt[s[left] - 'a']--;
left++;
}
while (right - left + 1 > k) {
cnt[s[left] - 'a']--;
left++;
}
if (right - left + 1 == k) ans++;
}
return ans;
}
};class Solution:
def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
if k > len(s):
return 0
cnt = [0] * 26
left = 0
ans = 0
for right, ch in enumerate(s):
r = ord(ch) - ord('a')
cnt[r] += 1
while cnt[r] > 1:
cnt[ord(s[left]) - ord('a')] -= 1
left += 1
while right - left + 1 > k:
cnt[ord(s[left]) - ord('a')] -= 1
left += 1
if right - left + 1 == k:
ans += 1
return ans/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var numKLenSubstrNoRepeats = function(s, k) {
if (k > s.length) return 0;
const cnt = new Array(26).fill(0);
let left = 0;
let ans = 0;
for (let right = 0; right < s.length; right++) {
const r = s.charCodeAt(right) - 97;
cnt[r]++;
while (cnt[r] > 1) {
cnt[s.charCodeAt(left) - 97]--;
left++;
}
while (right - left + 1 > k) {
cnt[s.charCodeAt(left) - 97]--;
left++;
}
if (right - left + 1 === k) {
ans++;
}
}
return ans;
};
Comments