Count With K Different Characters

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
203 upvotes
Asked in companies
CiscoWalmartGoogle

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1 :

aacfssa    
3

Sample Output 1 :

5

Explanation of The Sample Input 1:

Given 'str' = “aacfssa”. We can see that the substrings with only 3 distinct characters are {aacf, acf, cfs, cfss, fssa}. 

Therefore, the answer will be 5.

Sample Input 2 :

qffds
4

Sample Output 2 :

1

Constraints:

1 <= |str| <= 10^5
1 <= k <= 26

Time Limit: 1 second
Hint

Can you check for all the possible substrings?

Approaches (3)
Brute Force

 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.
Time Complexity

O(N ^ 3), where ‘N’ denotes the length of the given string.

 

We are calculating all possible substrings of the string and then we are calculating the count of characters in each substring. So, the time complexity will be O(N ^ 3)(for calculating every substring)  + O(N)(for counting) = O(N ^ 3).

Space Complexity

O(N), where ‘N’ denotes the length of the given string.

 

Since we are using a hashmap for storing the string characters, the net space complexity will be O(N).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Count With K Different Characters
Full screen
Console