⚡Flashcard Drill➔
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

  1. Maintain the longest window ending at the current position that contains no repeated characters.
  2. When the window length equals k, it is exactly a valid length-k substring, so increment the count.
  3. The window is maintained with a frequency map plus a shrink loop.
  4. 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 >= k for the length check: a longer window would be counted, but only windows of exactly k qualify -- 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 length k anyway.
  • 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems