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 length K and count distinct characters.
Use a set to keep track of distinct characters in each substring.
Increment count if number of distinct characters equals K.

Count Substrings with K Distinct Characters

Input:

Output:

Example:

Constraints:

Top CommVault Full Stack Developer interview questions & answers

Popular interview questions of Full Stack Developer