Count with K different characters

PROBLEM STATEMENT

You are given a string ‘STR’ of lowercase alphabets and an integer K. Your task is to count all the possible substrings that are not necessarily distinct but should 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 of input contains an integer T’ denoting the number of test cases.

The first and the only line of each test case contains a string ‘STR’.

The second line of each test case contains a single integer K.

Output format :

For each test case, in a separate line, return a single integer which is the count of all possible substrings having exactly K distinct characters.

Note:

You don’t have to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= |STR| <= 3*10^3
1 <= K <= 26

Time Limit: 1 second

Approach 1

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.

Try Problem

Approach 2

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

Try Problem

Approach 3

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.

Try Problem