NeetCode #228LC-1100MediumSliding WindowNC Algo100
← Back to All Problems#228 · #1100 · Find K-Length Substrings With No Repeated Characters(长度为 K 的无重复字符子串)
📌 Problem Statement & Constraints
Given a string
s and an integer k, return the number of substrings of length k with no repeated characters. Constraints: 1 <= s.length <= 10^4, 1 <= k <= s.length; s consists of lowercase letters.💡 Core Algorithmic Approaches
- Maintain the longest window ending at the current position that contains no repeated characters.
- When the window length equals
k, it is exactly a valid length-ksubstring, so increment the count. - The window is maintained with a frequency map plus a shrink loop.
- An alternative uses a set with last-seen indices, jumping the left pointer directly.
💻 Benchmark Python3 Implementation
class Solution:
def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
from collections import Counter
if k > len(s):
return 0
cnt = Counter()
l = 0
res = 0
for r, ch in enumerate(s):
cnt[ch] += 1
while cnt[ch] > 1: # duplicate -> shrink
cnt[s[l]] -= 1
l += 1
if r - l + 1 == k: # window is exactly k and all unique
res += 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each character enters and leaves the window at most once.
💾 Space Complexity
O(k) for the counter.
⚠️ Interview Pitfalls & Follow-ups
- Using
>= kfor the length check: a longer window would be counted, but only windows of exactlykqualify -- and the window here is the longest unique one, so equality is the right test. - Counting windows of length k with duplicates: the shrink loop guarantees uniqueness.
- Forgetting the
k > len(s)guard: the answer is 0, and the loop would never reach a window of lengthkanyway. - Using a set instead of a counter: a set works for uniqueness but requires the shrink loop to re-add characters correctly; the counter is clearer.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner