# 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.