Problem of the day
'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.
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.
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.
You don’t have to print anything; it has already been taken care of. Just implement the given function.
1 <= T <= 5
1 <= |STR| <= 3*10^3
1 <= K <= 26
Time Limit: 1 second
2
cdc
2
aacfssa
3
3
5
For the first test case:
Given STR = "cdc”, we can see that the substrings with only 2 distinct characters are {cd, dc, cdc}. Therefore, the answer will be 3.
For the second test case:
Given STR = “aacfssa”. We can see that the substrings with only 3 distinct characters are {acf, cfs, aacf, cfss, fssa}. Therefore, the answer will be 5.
3
aakash
2
bbbb
1
qffds
5
7
10
0