Count Substrings with K Distinct Characters

Given a lowercase string 'STR' and an integer K, the task is to count all possible substrings that consist of exactly K distinct characters. These substrings are not required to be distinct.

Input:

'STR' = “abcad”, K = 2

Output:

4

Example:

For the given string 'STR' = “abcad” and K = 2, the substrings {ab, bc, ca, ad} each have 2 distinct characters. Therefore, the total count is 4.

Constraints:

1

Question

Count Substrings with K Distinct Characters

Given a lowercase string 'STR' and an integer K, the task is to count all possible substrings that consist of exactly K distinct characters. These substrings are not required to be distinct.

Input:

'STR' = “abcad”, K = 2

Output:

Example:

For the given string 'STR' = “abcad” and K = 2, the substrings {ab, bc, ca, ad} each have 2 distinct characters. Therefore, the total count is 4.

Constraints:

1 <= T <= 5
1 <= |STR| <= 3 * 10^3
1 <= K <= 26
Time Limit: 1 second

Accepted Answer

Count substrings with exactly K distinct characters in a given lowercase string.

Iterate through all substrings of the given string and count the number of distinct characters in each substring.
Keep track of substrings with exactly K distinct characters and increment the count.
Return the total count of substrings with exactly K distinct characters.

Count Substrings with K Distinct Characters

Input:

Output:

Example:

Constraints:

Publicis Sapient Junior Associate interview questions & answers

Popular interview questions of Junior Associate