Count with K different characters

Posted: 27 Feb, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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