Problem Description

You are given a string S and an integer K. Your task is to find how many substrings of length K in S contain no repeated characters.

A substring is a contiguous sequence of characters within the string. The substrings must be exactly of length K, and each character within such a substring must be unique (i.e., no character appears more than once in the substring).

Constraints:

• 1 ≤ K ≤ length of S ≤ 10⁴
• S consists of only lowercase English letters

Thought Process

The straightforward approach is to check every possible substring of length K in S and determine if all its characters are unique. However, since there can be up to O(N) such substrings (where N is the length of S), and checking each substring for uniqueness could take up to O(K) time, this brute-force solution may be too slow for large inputs.

To optimize, we can use a sliding window approach. Instead of checking each substring from scratch, we can slide a window of size K across the string, efficiently tracking the characters in the current window and whether any duplicates exist. This way, we avoid redundant work and can check each substring in constant time using a hash set or array.

Solution Approach

We use a sliding window of length K and a data structure to keep track of the characters inside the window. Here is a step-by-step breakdown:

1. Initialization:
   • Start with an empty set (or an array of size 26 for lowercase letters) to record the characters in the current window.
   • Set two pointers, left and right, to define the current window's bounds.
2. Sliding the Window:
   • Move the right pointer forward, adding the current character to the set.
   • If the window size exceeds K, remove the character at left from the set and increment left.
3. Checking for Uniqueness:
   • Whenever the window reaches size K, check if the set size is K (i.e., all characters are unique).
   • If so, increment a counter.
4. Continue Sliding:
   • Repeat the process until the right pointer reaches the end of the string.

We use a hash set (or an array for character counts) because it allows O(1) insertion, deletion, and existence checks, making the algorithm efficient.

Example Walkthrough

Example Input: S = "havefunonleetcode", K = 5

• Start with an empty window and slide it across the string.
• First window: "havef" (positions 0–4). All characters are unique, so count = 1.
• Next window: "avefu" (positions 1–5). All unique, count = 2.
• Continue: "vefun" (2–6), "efuno" (3–7), "funon" (4–8): "funon" has two 'n's, so not unique, count remains 4.
• Continue sliding, updating the set and checking uniqueness at each step.
• Final answer: 6 substrings of length 5 with all unique characters.

At each step, we efficiently add the new character and remove the old one, checking if the window contains all unique characters.

Time and Space Complexity

Brute-force approach:

• Time: O(NK), since we check every substring (O(N)) and check for uniqueness (O(K)).
• Space: O(K), for storing characters of each substring.

• Time: O(N), since each character is added and removed from the set at most once.
• Space: O(K) or O(1), because the set holds at most K characters (or 26 for lowercase letters).

This makes the sliding window solution efficient even for large input strings.

Summary

By leveraging a sliding window and a hash set (or array) to track unique characters, we can efficiently count all substrings of length K with no repeated characters in a single pass through the string. This approach avoids redundant checks and runs in linear time, making it both elegant and practical for large strings.

Code Implementation

class Solution:
    def numKLenSubstrNoRepeats(self, S: str, K: int) -> int:
        if K > len(S):
            return 0
        count = 0
        seen = set()
        left = 0
        for right in range(len(S)):
            while S[right] in seen:
                seen.remove(S[left])
                left += 1
            seen.add(S[right])
            if right - left + 1 == K:
                count += 1
                seen.remove(S[left])
                left += 1
        return count
      

class Solution {
public:
    int numKLenSubstrNoRepeats(string S, int K) {
        if (K > S.size()) return 0;
        int count = 0;
        unordered_set<char> seen;
        int left = 0;
        for (int right = 0; right < S.size(); ++right) {
            while (seen.count(S[right])) {
                seen.erase(S[left]);
                left++;
            }
            seen.insert(S[right]);
            if (right - left + 1 == K) {
                count++;
                seen.erase(S[left]);
                left++;
            }
        }
        return count;
    }
};
      

class Solution {
    public int numKLenSubstrNoRepeats(String S, int K) {
        if (K > S.length()) return 0;
        int count = 0;
        Set<Character> seen = new HashSet<>();
        int left = 0;
        for (int right = 0; right < S.length(); right++) {
            while (seen.contains(S.charAt(right))) {
                seen.remove(S.charAt(left));
                left++;
            }
            seen.add(S.charAt(right));
            if (right - left + 1 == K) {
                count++;
                seen.remove(S.charAt(left));
                left++;
            }
        }
        return count;
    }
}
      

var numKLenSubstrNoRepeats = function(S, K) {
    if (K > S.length) return 0;
    let count = 0;
    let seen = new Set();
    let left = 0;
    for (let right = 0; right < S.length; right++) {
        while (seen.has(S[right])) {
            seen.delete(S[left]);
            left++;
        }
        seen.add(S[right]);
        if (right - left + 1 === K) {
            count++;
            seen.delete(S[left]);
            left++;
        }
    }
    return count;
};