1100. Find K-Length Substrings With No Repeated Characters

MediumHash TableStringSliding Window
Leetcode Link

Problem Description

Given a string s and an integer k, the task is to count how many substrings of length k exist within s that contain no repeated characters. A substring is a contiguous sequence of characters within a string. For example, in the string abcde, abc, bcd, and cde are substrings of length 3. We are specifically interested in substrings where every character is unique, meaning no character appears more than once in that substring.

Intuition

The intuition behind the solution is to use the "sliding window" technique. This approach involves maintaining a window of characters that can expand or shrink as needed while scanning the string from left to right. Here's how the intuition develops:

  1. If k is greater than the length of the string or if k is greater than 26 (the number of letters in the English alphabet), there can't be any valid substrings of length k with all unique characters, so we return 0 immediately.

  2. Starting at the beginning of the string, we expand our window to include characters until we hit a size of k or we find a duplicate character.

  3. To efficiently keep track of the characters inside our current window and their counts, we use a Counter (a type of dictionary or hashmap in Python), incrementing the count for each new character we add to the window.

  4. If at any point a character's count exceeds 1 (meaning we've found a duplicate), or the window's size exceeds k, we shrink the window from the left by removing characters and decrementing their respective counts.

  5. Every time our window size becomes exactly k and all characters are unique (i.e., no count is greater than 1), we have found a valid substring. We then increment the counter for the final answer (ans).

Notice that for each position i in the string, we adjust the left side of our window (j) to ensure the window size does not exceed k and there are no repeating characters. The solution iteratively keeps account of all such substrings and returns the count as the final result.

Learn more about Sliding Window patterns.

Solution Approach

The solution employs the sliding window approach along with a Counter from the collections module to keep track of the number of occurrences of each character within the current window. Here's a step-by-step breakdown:

  1. Initialize Variables: A counter named cnt is used to count occurrences of characters, ans for storing the total count of valid substrings found, and j for marking the start position of the sliding window.

  2. Early Termination Checks: Check if k is larger than the string length n or greater than 26. If so, we return 0 because it's not possible to have substrings of length k with unique characters.

  3. Iterate Over the String: Use a for-loop with enumerate(s) to get both index i and character c.

  4. Expand the Window: Increase the count of the current character c in cnt.

  5. Shrink the Window if Necessary: a. While the count of character c in cnt is more than 1 (meaning c has appeared before in the current window), decrease the count of the leftmost character s[j] and increase j to move the window's left edge to the right. b. Also, shrink the window if the current window length (i - j + 1) exceeds k.

  6. Check Window Validity: If the window length is exactly k, and all characters in the window are unique (the while loop has ensured that the counts are 1), increment ans which signifies a valid substring.

  7. Return Result: After finishing the loop, the ans variable contains the number of substrings with length k and no repeating characters, which is returned as the solution.

This solution uses a dynamic slide of the window that only moves the left bound forward (j), and never backward, ensuring that the algorithm's time complexity is O(n), as each character is processed at most twice (once when added to the window, once when removed). This makes the algorithm efficient for this problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search can be used to find whether two components in a graph are connected.

Example Walkthrough

Let's illustrate the solution approach with a concrete example. Consider the string s = "abcba" and k = 3. We want to find the total number of valid substrings of length 3 with no repeating characters.

  1. Initialize Variables: Initialize cnt = Counter(), ans = 0, j = 0.

  2. Early Termination Checks: Length of s is 5, and k is 3, which is less than 26, so we move on without terminating early.

  3. Iterate Over the String: We start a for-loop that iterates over each character.

    • On the first iteration i = 0, c = 'a'. We add 'a' to the counter.
    • Then, the window size is 1, which is less than 3. Since there are no duplicates, we continue.
  4. On the second iteration i = 1, c = 'b'. We add 'b' to the counter.

    • Now the window size is 2, which is still less than 3. No duplicates so, we continue.
  5. In the third iteration i = 2, c = 'c'. We add 'c' to the counter.

    • Our window is now abc (i - j + 1 = 3), which is equal to k and contains no repeating characters.
    • We found a valid substring, so ans = ans + 1.
  6. Fourth iteration i = 3, c = 'b'. Counter for 'b' becomes 2, indicating a duplicate.

    • We proceed to shrink the window. We reduce the count of 'a' since it's the leftmost character in the current window and move j from 0 to 1.
    • The window length is again 3 after adjusting j, but now it's bcb which is not valid because it contains repeating characters 'b'.
  7. Fifth iteration i = 4, c = 'a'. The counter for 'a' is now 2, another duplicate.

    • Continuing to shrink the window, we decrease the count for 'b' and increment j to 2.
    • The window size (i - j + 1 = 3 - 2 + 1) now becomes 2. Since it's less than k, we continue to expand the window in the next iterations.
  8. At this point, the substring cba from the previous steps is no longer in our current window. We have a window of size 2 with unique characters cb. Unfortunately, this is the last iteration, and there are no more characters in s to consider.

  9. Return Result: No other valid substrings of length 3 are found, so the final ans remains 1.

In conclusion, there is only one valid substring of length 3 with all unique characters in the string abcba, which is abc. Hence the function would return 1.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def numKLenSubstrNoRepeats(self, string: str, k: int) -> int:
5        # Calculate the length of the input string
6        length_of_string = len(string)
7      
8        # If the required substring length k is greater than the string length
9        # or greater than the alphabet count, there can be no valid substrings.
10        if k > length_of_string or k > 26:
11            return 0
12      
13        # Initialize the answer to 0 and the start index of the current substring to 0
14        num_of_substrings = current_start_index = 0
15      
16        # Create a Counter to store the frequency of characters in the current substring
17        char_freq = Counter()
18      
19        # Iterate through the string using the index and character
20        for current_end_index, char in enumerate(string):
21            # Increment the frequency of the current character
22            char_freq[char] += 1
23          
24            # While there are duplicate characters in the current substring,
25            # or the substring length exceeds k, shrink the substring from the left.
26            while char_freq[char] > 1 or current_end_index - current_start_index + 1 > k:
27                char_freq[string[current_start_index]] -= 1
28                current_start_index += 1
29          
30            # If the current substring length is exactly k, we found a valid substring.
31            if current_end_index - current_start_index + 1 == k:
32                num_of_substrings += 1
33      
34        # Return the total count of valid substrings
35        return num_of_substrings
36
1class Solution {
2
3    // Method to count the number of k-length substrings with no repeating characters
4    public int numKLenSubstrNoRepeats(String s, int k) {
5
6        // Get the length of the string
7        int stringLength = s.length();
8
9        // If k is greater than the string length or the maximum possible unique characters, return 0
10        if (k > stringLength || k > 26) {
11            return 0;
12        }
13
14        // Create an array to store the count of characters
15        int[] charCount = new int[128];
16      
17        // Initialize a variable to store the count of valid substrings
18        int validSubstrCount = 0;
19
20        // Initialize two pointers for the sliding window technique
21        for (int start = 0, end = 0; end < stringLength; ++end) {
22
23            // Increment the count of the current character
24            charCount[s.charAt(end)]++;
25
26            // If a character count is greater than 1, or the window size is greater than k,
27            // then slide the window from the start
28            while (charCount[s.charAt(end)] > 1 || end - start + 1 > k) {
29                // Decrement the count of the starting character as it is no longer in the window
30                charCount[s.charAt(start++)]--;
31            }
32
33            // If the size of the window equals k, we have a valid substring
34            validSubstrCount += end - start + 1 == k ? 1 : 0;
35        }
36
37        // Return the total count of valid substrings
38        return validSubstrCount;
39    }
40}
41
1class Solution {
2public:
3    int numKLenSubstrNoRepeats(string s, int k) {
4        int strLength = s.size();
5
6        // If the length of the substring `k` is greater than the string length 
7        // or there are more characters than the alphabet size, return 0
8        // because no such substrings can exist.
9        if (k > strLength || k > 26) {
10            return 0;
11        }
12      
13        // Array to keep count of character occurrences
14        int charCount[128] = {}; // Initialize all elements to 0
15        int validSubstrCount = 0; // Counter for the number of valid substrings
16
17        // Use a sliding window defined by the range [windowStart, windowEnd]
18        for (int windowEnd = 0, windowStart = 0; windowEnd < strLength; ++windowEnd) {
19            // Increase the count for the current character at windowEnd
20            ++charCount[s[windowEnd]];
21          
22            // If there is a duplicate character or the window size exceeds k,
23            // shrink the window from the left by increasing windowStart.
24            while (charCount[s[windowEnd]] > 1 || windowEnd - windowStart + 1 > k) {
25                --charCount[s[windowStart++]];
26            }
27          
28            // If the window size is exactly k, we found a valid substring without repeating characters.
29            // Increase the count of valid substrings.
30            validSubstrCount += (windowEnd - windowStart + 1) == k;
31        }
32
33        // Return the total count of valid substrings found
34        return validSubstrCount;
35    }
36};
37
1function numKLenSubstrNoRepeats(s: string, k: number): number {
2    // Calculate the length of the input string.
3    const stringLength = s.length;
4
5    // If the requested substring length is greater than the string length, return 0.
6    if (k > stringLength) {
7        return 0;
8    }
9
10    // Map to store the frequency of characters in the current window.
11    const frequencyMap: Map<string, number> = new Map();
12
13    // Initialize the frequency map with the first 'k' characters of the string.
14    for (let index = 0; index < k; ++index) {
15        frequencyMap.set(s[index], (frequencyMap.get(s[index]) ?? 0) + 1);
16    }
17
18    // Count valid substrings. A valid substring has no repeated characters.
19    let validSubstringCount = frequencyMap.size === k ? 1 : 0;
20
21    // Iterate over the string, starting from the 'k'th character.
22    for (let index = k; index < stringLength; ++index) {
23        // Add the current character to the map.
24        frequencyMap.set(s[index], (frequencyMap.get(s[index]) ?? 0) + 1);
25        // Remove or decrement the character count 'k' positions behind.
26        frequencyMap.set(s[index - k], (frequencyMap.get(s[index - k]) ?? 0) - 1);
27
28        // If the count of the old character drops to zero, remove it from the map.
29        if (frequencyMap.get(s[index - k]) === 0) {
30            frequencyMap.delete(s[index - k]);
31        }
32
33        // If the current window has exactly 'k' unique characters, increment the result.
34        validSubstringCount += frequencyMap.size === k ? 1 : 0;
35    }
36
37    // Return the total count of valid substrings.
38    return validSubstringCount;
39}
40

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the string s. This is because the code uses a sliding window approach, traversing the string once. Each character is added to the sliding window, and if a condition is met (more than one occurrence of the same character, or the window size exceeds k), the window adjusts by removing characters from the start. The number of adjustments made is proportional to n as well.

The space complexity of the code is O(k) if k < 26, or O(26) (which simplifies to O(1)) if k >= 26, due to the length of the Counter dictionary never having more characters than the alphabet case (k characters when k < 26, and 26 characters of the alphabet when k >= 26 because no more than 26 unique characters can be in the string at a time given it consists of just the alphabet).

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


Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄