LeetCode 1100: Find K-Length Substrings With No Repeated Characters

Problem Restatement

We are given a string s and an integer k.

Return the number of substrings of length k with no repeated characters.

The official constraints state that 1 <= s.length <= 10^4 and 1 <= k <= 26.

Input and Output

Function shape:

def numKLenSubstrNoRepeats(s: str, k: int) -> int:
    ...

Examples

Example 1:

s = "havefunonleetcode"
k = 5

The length-5 substrings with no repeated characters are "havef", "avefu", "vefun", "efuno", "etcod", and "tcode". There are 6 valid substrings.

Answer:

6

Key Insight

Use a sliding window of size k. Maintain a character frequency count. If all characters in the window are distinct (frequency count has exactly k unique characters), count it.

Alternatively: if the window has no character with frequency > 1, it is valid.

Algorithm

1. If k > 26, return 0 (impossible).
2. Use a sliding window of size k with a character counter.
3. Count valid windows where all character frequencies are exactly 1.

Edge Cases

• Handle windows that never become valid.
• Update counts when both expanding and shrinking the window so stale characters do not remain in the state.
• For fixed-size windows, record the answer only after the window has exactly the required length.

Complexity

Common Pitfalls

• Do not count a window before it satisfies the required size or validity condition.
• When removing the left character, delete zero-count entries if the algorithm uses the number of keys.

Implementation

from collections import Counter

class Solution:
    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
        if k > len(s):
            return 0

        count = Counter(s[:k])
        result = 1 if len(count) == k else 0

        for i in range(k, len(s)):
            count[s[i]] += 1
            count[s[i - k]] -= 1
            if count[s[i - k]] == 0:
                del count[s[i - k]]
            if len(count) == k:
                result += 1

        return result

Testing

def run_tests():
    s = Solution()

    assert s.numKLenSubstrNoRepeats("havefunonleetcode", 5) == 6
    assert s.numKLenSubstrNoRepeats("home", 5) == 0
    assert s.numKLenSubstrNoRepeats("abcabc", 3) == 4

    print("all tests passed")

run_tests()