Count with K different characters

Posted: 27 Feb, 2021
Difficulty: Easy

PROBLEM STATEMENT

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.