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 <= T <= 5
• 1 <= |STR| <= 3 * 10^3
• 1 <= K <= 26
• Time Limit: 1 second