Unique Substrings with Exactly K Distinct Characters

You are given a string S and an integer K. Your task is to find the number of substrings of S that contain exactly K distinct characters. A substring is a contiguous block of characters within the string. Note that substrings with the same content but occurring at different positions are counted separately.

The problem can be solved by using a two-pointer (sliding window) technique to count the number of substrings with at most K distinct characters, and then subtracting the count of substrings with at most K-1 distinct characters. Mathematically, the answer is given by:

\[ \text{Answer}(S, K) = f(S, K) - f(S, K-1), \]

where \(f(S, k)\) is the number of substrings with at most \(k\) distinct characters.

inputFormat

The first line of the input contains an integer T representing the number of test cases. Each test case consists of two lines:

• The first line contains the string S.
• The second line contains an integer K.

It is guaranteed that S is non-empty and contains only printable characters.

outputFormat

For each test case, output a single line containing the number of substrings of S that have exactly K distinct characters.

5
abcabc
2
aaa
1
abcdef
2
aaaaa
2
abac
2

5
6
5
0
4