Problem Description

You are given a string s and an integer k. Your task is to find how many substrings of length k exist in the string s where all characters in the substring are unique (no repeated characters).

A substring is a contiguous sequence of characters within the string. For example, in the string "abc", the substrings of length 2 are "ab" and "bc".

The key requirement is that each substring must:

1. Have exactly k characters
2. Contain no duplicate characters (all characters must be different)

For instance, if s = "havefunonleetcode" and k = 5, you would check all consecutive 5-character windows in the string. The substring "havef" has all unique characters, so it counts. The substring "avefu" also has all unique characters. But a substring like "eeton" would not count because it contains two 'e' characters.

The function should return the total count of such valid substrings.

Intuition

The core insight is that we need to check every possible substring of length k in the string. A naive approach would be to examine each substring individually, checking if it has all unique characters. However, this would involve redundant work since consecutive substrings overlap significantly.

Consider two consecutive substrings of length k: one starting at position i and another at position i+1. These substrings share k-1 characters. The only difference is that the second substring loses the first character of the previous window and gains one new character at the end.

This observation naturally leads to a sliding window approach. We can maintain a window of size k and slide it across the string one position at a time. Instead of rechecking all k characters each time, we only need to:

1. Remove the character that's leaving the window (the leftmost character)
2. Add the character that's entering the window (the new rightmost character)

To efficiently track whether all characters in our window are unique, we can use a hash table (or Counter in Python) that stores the frequency of each character in the current window. The key realization is that if the hash table has exactly k entries, it means all k characters in the window are different (since each unique character would have its own entry).

When we slide the window:

• We increment the count for the new character entering
• We decrement the count for the character leaving
• If a character's count drops to 0, we remove it from the hash table entirely

This way, we can check if the current window has all unique characters in constant time by simply checking if len(cnt) == k.

Learn more about Sliding Window patterns.

Solution Approach

We implement a sliding window technique combined with a hash table to efficiently count valid substrings.

Initial Window Setup: First, we create a Counter (hash table) cnt to store the frequency of characters in our current window. We initialize it with the first k characters of the string: cnt = Counter(s[:k]).

We then check if this initial window has all unique characters by verifying if len(cnt) == k. If the hash table has exactly k entries, it means all characters are different, so we initialize our answer ans accordingly: ans = int(len(cnt) == k).

Sliding the Window: We iterate through the string starting from index k to the end. For each position i:

1. Add the new character: We add the character entering the window s[i] to our counter: cnt[s[i]] += 1

2. Remove the old character: We decrement the count of the character leaving the window s[i - k]: cnt[s[i - k]] -= 1

3. Clean up the hash table: If the count of the leaving character becomes 0, we remove it entirely from the hash table:

   if cnt[s[i - k]] == 0:
       cnt.pop(s[i - k])

4. Check validity: After updating the window, we check if all characters in the current window are unique by verifying if len(cnt) == k. If true, we increment our answer: ans += int(len(cnt) == k)

Why this works: The hash table size equals k only when we have exactly k different characters, each appearing once. If any character appears more than once, the hash table would have fewer than k entries (since multiple occurrences of the same character share one entry with a count greater than 1).

Time and Space Complexity:

• Time: O(n) where n is the length of string s, as we visit each character once
• Space: O(k) for the hash table, which stores at most k different characters

Example Walkthrough

Let's walk through the solution with s = "abcabc" and k = 3.

Step 1: Initialize the window with first k characters

• Initial window: "abc" (indices 0-2)
• Create Counter: cnt = {'a': 1, 'b': 1, 'c': 1}
• Check if valid: len(cnt) = 3 = k ✓ (all characters are unique)
• Initialize ans = 1

Step 2: Slide window to position 3

• New character entering: s[3] = 'a'
• Character leaving: s[0] = 'a'
• Add new character: cnt['a'] = 1 + 1 = 2
• Current counter: cnt = {'a': 2, 'b': 1, 'c': 1}
• Remove old character: cnt['a'] = 2 - 1 = 1
• Final counter: cnt = {'a': 1, 'b': 1, 'c': 1}
• Current window: "bca" (indices 1-3)
• Check if valid: len(cnt) = 3 = k ✓
• Update ans = 2

Step 3: Slide window to position 4

• New character entering: s[4] = 'b'
• Character leaving: s[1] = 'b'
• Add new character: cnt['b'] = 1 + 1 = 2
• Current counter: cnt = {'a': 1, 'b': 2, 'c': 1}
• Remove old character: cnt['b'] = 2 - 1 = 1
• Final counter: cnt = {'a': 1, 'b': 1, 'c': 1}
• Current window: "cab" (indices 2-4)
• Check if valid: len(cnt) = 3 = k ✓
• Update ans = 3

Step 4: Slide window to position 5

• New character entering: s[5] = 'c'
• Character leaving: s[2] = 'c'
• Add new character: cnt['c'] = 1 + 1 = 2
• Current counter: cnt = {'a': 1, 'b': 1, 'c': 2}
• Remove old character: cnt['c'] = 2 - 1 = 1
• Final counter: cnt = {'a': 1, 'b': 1, 'c': 1}
• Current window: "abc" (indices 3-5)
• Check if valid: len(cnt) = 3 = k ✓
• Update ans = 4

Final Result: 4 valid substrings

All four substrings of length 3 have unique characters: "abc", "bca", "cab", "abc".

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s.

The algorithm initializes a counter for the first k characters, which takes O(k) time. Then it performs a sliding window operation that iterates through the remaining n - k characters. For each iteration, it performs constant-time operations: adding one character to the counter, decrementing the count of another character, potentially removing an element from the counter, and checking the counter's size. Since each character is processed exactly once after the initial window setup, the total time complexity is O(k) + O(n - k) = O(n).

Space Complexity: O(min(k, |Σ|)), where |Σ| is the size of the character set.

The counter stores at most k distinct characters (the size of the window), but it's also bounded by the total number of possible distinct characters in the string. Since the problem uses lowercase English letters, |Σ| = 26. Therefore, the counter can have at most min(k, 26) entries at any given time, resulting in a space complexity of O(min(k, |Σ|)).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Edge Cases Where k > len(s)

One of the most common mistakes is not checking if k is larger than the length of the string. When k > len(s), it's impossible to have any substring of length k, and the code would crash when trying to initialize the counter with s[:k].

Problematic Code:

def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
    char_count = Counter(s[:k])  # This fails if k > len(s)
    # rest of the code...

Solution: Add an early return check at the beginning of the function:

def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
    if k > len(s):
        return 0
  
    char_count = Counter(s[:k])
    # rest of the code...

2. Incorrectly Checking for Unique Characters

A subtle mistake is checking if the counter values are all equal to 1 instead of checking the counter's size. This leads to unnecessary iteration through the counter.

Inefficient Approach:

# Wrong: Checking all values in counter
result += int(all(count == 1 for count in char_count.values()))

Correct Approach:

# Right: Simply check the size of the counter
result += int(len(char_count) == k)

The correct approach works because if any character appears more than once, the counter will have fewer than k keys (multiple occurrences share the same key with count > 1).

3. Forgetting to Remove Zero-Count Characters

Failing to remove characters with zero count from the counter leads to incorrect results, as these "ghost" entries affect the length check.

Incorrect Code:

for i in range(k, len(s)):
    char_count[s[i]] += 1
    char_count[s[i - k]] -= 1
    # Missing: removal of zero-count entries
    result += int(len(char_count) == k)  # This will be wrong!

Correct Code:

for i in range(k, len(s)):
    char_count[s[i]] += 1
    char_count[s[i - k]] -= 1
  
    # Essential: Remove character if count becomes 0
    if char_count[s[i - k]] == 0:
        char_count.pop(s[i - k])
  
    result += int(len(char_count) == k)

4. Using Wrong Window Boundaries

A common indexing error is using incorrect boundaries when sliding the window, such as s[i - k + 1] instead of s[i - k].

Wrong:

char_count[s[i - k + 1]] -= 1  # This keeps wrong character in window

Correct:

char_count[s[i - k]] -= 1  # Removes the character that's k positions behind

5. Not Considering k = 0 or k = 1 Cases

While k = 0 might not be a valid input in most problems, k = 1 is a special case where every single character forms a valid substring (since a single character is always unique).

Enhanced Solution with All Edge Cases:

def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
    # Handle edge cases
    if k > len(s) or k <= 0:
        return 0
    if k == 1:
        return len(s)
  
    # Main sliding window logic
    char_count = Counter(s[:k])
    result = int(len(char_count) == k)
  
    for i in range(k, len(s)):
        char_count[s[i]] += 1
        char_count[s[i - k]] -= 1
      
        if char_count[s[i - k]] == 0:
            char_count.pop(s[i - k])
      
        result += int(len(char_count) == k)
  
    return result