Last Updated: 27 Feb, 2021
Count With K Different Characters
Moderate
Asked in companies
You are given a string 'str' of lowercase alphabets and an integer 'k' .
Your task is to return the count all the possible substrings that have exactly 'k' distinct characters.
For example:
'str' = abcad and 'k' = 2.
We can see that the substrings {ab, bc, ca, ad} are the only substrings with 2 distinct characters.
Therefore, the answer will be 4.
Input format :
The first line contains a string ‘str’.
The second line contains a single integer 'k'.
Output format :
The output contains a single integer which is the count of all possible substrings having exactly 'k' distinct characters.
Note:
You don’t have to print anything. Just implement the given function.
Approaches
The idea is to check for all the substrings of the given string and then check for each substring whether it contains exactly K different characters or not.
- Declare COUNT = 0 for storing the answer.
- Run two nested loops for generating the indices of all the substrings of the string say i and j (i starting from 0 and j starting from i).
- Take the substring from index i to j.
- Check for the characters in the substring i.e. count the number of different characters in the substring.
- Declare a hashmap ‘HASH_MAP'
- Count the frequency of each character in the substring i.e. put the key and value of each character in the HASH_MAP.
- Now, COUNT the number of keys in the HASH_MAP. If the number of keys in the 'HASH_MAP' is equal to K, than increment the COUNT because keys will give the total distinct characters present.
- Else move to the next iteration.
- Return COUNT.
The idea is the same as the previous approach to check for all the substrings of the given string and then check for each substring whether it contains exactly K different characters or not. Here, we will use an array of 26 length to store the count of each character in the substring.
- Declare an array 'COUNT' of length 26 to store the count of characters from ‘a’ to ‘z’ and a variable RESULT = 0 for the answer.
- Run two nested loops for generating the indices of all the substrings of the string say i and j (i starting from 0 and j starting from i).
- For each substring, fill the 'COUNT' array with zeros for every ith iteration.
- Declare a variable DISTINCT_CHARS = 0 to count the distinct characters in substrings.
- Now, count the unique characters and check if that character is appearing for the first time or not. If yes, then increase the DISTINCT_CHARS and count in the array at that index.
- Check if the DISTINCT_CHARS is equal to K increment the result.
- Finally, after the loops return the result
The idea is to use a sliding window to count the number of substrings with at most K different characters because finding substrings with exactly K characters will again cost us N ^ 2 times. Therefore we will count as the number of substrings with exactly K different characters will be the number of substrings with at most K different characters - number of substrings with at most (K-1) different characters.
- Declare a helper function HELPER to count substrings with at most K different characters.
- Declare two indices i and j starting from zero and CURR_COUNT = 0(for storing the count of different characters in the substring).
- Declare an array COUNT of length 26 to store the count of characters from ‘a’ to ‘z’ and a variable RESULT = 0 for the answer.
- Now run a while loop and increment the COUNT for the characters in the COUNT array. If the COUNT is 1 for that particular character in the array, then increment the CURR_COUNT.
- If the CURR_COUNT is greater than K:
- While CURR_COUNT > K, decrease the count of that particular character in the COUNT array and if it becomes zero, then decrement CURR_COUNT and increase i th pointer for the substring.
- For result, add j - i + 1 (for the total substrings with at most K different characters.
- Increment jth pointer.
- Now, in the original function call the HELPER function for at-most K different characters and for at-most K-1 different characters i.e. HELPER(K) - HELPER(K-1).
- Return this difference.