Count K-Length Substrings With No Repeated Characters
Given a string S and an integer k, the task is to return the number of substrings in S of length k with no repeated characters.
Example:
Input: S = “havefunonleetcode”, k = 5
Output: 6
Explanation: There are 6 substrings they are: ‘havef’,’avefu’,’vefun’,’efuno’,’etcod’,’tcode’.Input: S = “home”, k = 5
Output: 0
Explanation: Notice k can be larger than the length of S. In this case, it is not possible to find any substring.
Approach:
We iterate over the input, expanding and contracting our window.
- Whenever the window has a repeating character, contract the window until there are no repeating characters.
- If length of window equals K, add 1 to count of good windows and then contract the window.
- This works because since we checked and got rid of repeating characters in step 1, our window of length K must NOT have any repeating characters.
- We contract our window in this step because we don’t want a window that has a length GREATER than K.
Below points we also have to keep in mind:
- Keep track of our window bounds with left and right.
- Use a frequency dictionary to keep track of how many times we’ve seen a character.
- Remember to access frequency dictionary freq[S[right]] and not just freq[right]
- Check if right – left + 1 == K because we’ve added right to our frequency dictionary but we haven’t actually incremented right yet
Steps-by-step approach:
- Initialize variables:
- Create an unordered_map to store the frequency of each character in the current window.
- Initialize result to 0, which will store the number of substrings of length K with no repeating characters.
- Initialize left and right pointers to 0, which will represent the current window.
- Slide the window:
- Iterate through the string S using the right pointer.
- For each character S[right], increment its frequency in the freq map.
- Remove duplicates:
- While the frequency of the current character S[right] is greater than 1 (i.e., there is a duplicate):
- Decrement the frequency of the leftmost character S[left] in the freq map.
- Increment the left pointer to move the left side of the window.
- Count good windows:
- If the size of the current window (right – left + 1) is equal to K, it means we have found a substring of length K with no repeating characters.
- Increment the result.
- Decrement the frequency of the leftmost character S[left] in the freq map and increment the left pointer to slide the window.
- Increment the right pointer:
- Increment the right pointer to move the right side of the window.
- Return the final result.
Below is the implementation of the above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to count substrings of length K with no
// repeating characters
int numKLenSubstrNoRepeats(const string& S, int K)
{
if (K > S.size()) {
return 0; // K cannot be larger than string length
}
// Use unordered_map to store character frequencies
unordered_map<char, int> freq;
int count_of_good_lenK_windows = 0;
int left = 0, right = 0;
while (right < S.size()) {
// Add character to frequency map
freq[S[right]]++;
// tep 1: Slide window until no duplicates**
while (freq[S[right]] > 1) {
// Remove character from left side of window
freq[S[left]]--;
left++;
}
// Step 2: Count good windows**
if (right - left + 1 == K) {
count_of_good_lenK_windows++;
// Move left window and adjust frequency
freq[S[left]]--;
left++;
}
right++;
}
return count_of_good_lenK_windows;
}
int main()
{
string S = "havefunonleetcode";
int K = 5;
int count = numKLenSubstrNoRepeats(S, K);
cout << "Number of substrings of length " << K
<< " with no repeating characters: " << count
<< endl;
return 0;
}
import java.util.HashMap;
public class Main {
// Function to count substrings of length K with no
// repeating characters
public static int numKLenSubstrNoRepeats(String S,
int K)
{
if (K > S.length()) {
return 0; // K cannot be larger than string
// length
}
// Use HashMap to store character frequencies
HashMap<Character, Integer> freq = new HashMap<>();
int count_of_good_lenK_windows = 0;
int left = 0, right = 0;
while (right < S.length()) {
// Add character to frequency map
freq.put(S.charAt(right),
freq.getOrDefault(S.charAt(right), 0)
+ 1);
// Step 1: Slide window until no duplicates
while (freq.get(S.charAt(right)) > 1) {
// Remove character from left side of window
freq.put(S.charAt(left),
freq.get(S.charAt(left)) - 1);
left++;
}
// Step 2: Count good windows
if (right - left + 1 == K) {
count_of_good_lenK_windows++;
// Move left window and adjust frequency
freq.put(S.charAt(left),
freq.get(S.charAt(left)) - 1);
left++;
}
right++;
}
return count_of_good_lenK_windows;
}
public static void main(String[] args)
{
String S = "havefunonleetcode";
int K = 5;
int count = numKLenSubstrNoRepeats(S, K);
System.out.println(
"Number of substrings of length " + K
+ " with no repeating characters: " + count);
}
}
// This code is contributed by Shivam Gupta
from collections import defaultdict
# Function to count substrings of length K with no repeating characters
def numKLenSubstrNoRepeats(S, K):
if K > len(S):
return 0 # K cannot be larger than string length
# Use defaultdict to store character frequencies
freq = defaultdict(int)
count_of_good_lenK_windows = 0
left = 0
right = 0
while right < len(S):
# Add character to frequency map
freq[S[right]] += 1
# Step 1: Slide window until no duplicates
while freq[S[right]] > 1:
# Remove character from left side of window
freq[S[left]] -= 1
left += 1
# Step 2: Count good windows
if right - left + 1 == K:
count_of_good_lenK_windows += 1
# Move left window and adjust frequency
freq[S[left]] -= 1
left += 1
right += 1
return count_of_good_lenK_windows
# Driver code
S = "havefunonleetcode"
K = 5
count = numKLenSubstrNoRepeats(S, K)
print(f"Number of substrings of length {K} with no repeating characters: {count}")
// Function to count substrings of length K with no repeating characters
function numKLenSubstrNoRepeats(S, K) {
if (K > S.length) {
return 0; // K cannot be larger than string length
}
// Use a Map to store character frequencies
const freq = new Map();
let count_of_good_lenK_windows = 0;
let left = 0, right = 0;
while (right < S.length) {
// Add character to frequency map
const rightChar = S[right];
freq.set(rightChar, (freq.get(rightChar) || 0) + 1);
// Step 1: Slide window until no duplicates
while (freq.get(rightChar) > 1) {
// Remove character from left side of window
const leftChar = S[left];
freq.set(leftChar, freq.get(leftChar) - 1);
left++;
}
// Step 2: Count good windows
if (right - left + 1 === K) {
count_of_good_lenK_windows++;
// Move left window and adjust frequency
const leftChar = S[left];
freq.set(leftChar, freq.get(leftChar) - 1);
left++;
}
right++;
}
return count_of_good_lenK_windows;
}
// Example usage
const S = "havefunonleetcode";
const K = 5;
const count = numKLenSubstrNoRepeats(S, K);
console.log(`Number of substrings of length ${K} with no repeating characters: ${count}`);
// This code is contributed by Yash Agarwal
Output
Number of substrings of length 5 with no repeating characters: 6
Time Complexity: O(n * K)
Auxiliary Space: O(min(n, K))