1100. Find K-Length Substrings With No Repeated Characters
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:
-
If
k
is greater than the length of the string or ifk
is greater than 26 (the number of letters in the English alphabet), there can't be any valid substrings of lengthk
with all unique characters, so we return 0 immediately. -
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. -
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. -
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. -
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:
-
Initialize Variables: A counter named
cnt
is used to count occurrences of characters,ans
for storing the total count of valid substrings found, andj
for marking the start position of the sliding window. -
Early Termination Checks: Check if
k
is larger than the string lengthn
or greater than 26. If so, we return0
because it's not possible to have substrings of lengthk
with unique characters. -
Iterate Over the String: Use a for-loop with
enumerate(s)
to get both indexi
and characterc
. -
Expand the Window: Increase the count of the current character
c
incnt
. -
Shrink the Window if Necessary: a. While the count of character
c
incnt
is more than1
(meaningc
has appeared before in the current window), decrease the count of the leftmost characters[j]
and increasej
to move the window's left edge to the right. b. Also, shrink the window if the current window length (i - j + 1
) exceedsk
. -
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 are1
), incrementans
which signifies a valid substring. -
Return Result: After finishing the loop, the
ans
variable contains the number of substrings with lengthk
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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.
-
Initialize Variables: Initialize
cnt = Counter()
,ans = 0
,j = 0
. -
Early Termination Checks: Length of
s
is 5, andk
is 3, which is less than 26, so we move on without terminating early. -
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 than3
. Since there are no duplicates, we continue.
- On the first iteration
-
On the second iteration
i = 1
,c = 'b'
. We add 'b' to the counter.- Now the window size is
2
, which is still less than3
. No duplicates so, we continue.
- Now the window size is
-
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 tok
and contains no repeating characters. - We found a valid substring, so
ans = ans + 1
.
- Our window is now
-
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
from0
to1
. - The window length is again
3
after adjustingj
, but now it'sbcb
which is not valid because it contains repeating characters 'b'.
- We proceed to shrink the window. We reduce the count of 'a' since it's the leftmost character in the current window and move
-
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
to2
. - The window size (
i - j + 1 = 3 - 2 + 1
) now becomes 2. Since it's less thank
, we continue to expand the window in the next iterations.
- Continuing to shrink the window, we decrease the count for 'b' and increment
-
At this point, the substring
cba
from the previous steps is no longer in our current window. We have a window of size2
with unique characterscb
. Unfortunately, this is the last iteration, and there are no more characters ins
to consider. -
Return Result: No other valid substrings of length
3
are found, so the finalans
remains1
.
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.
Which technique can we use to find the middle of a linked list?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.