Substrings with Exactly K Distinct Characters

Given a string s and an integer k, count the number of substrings of s that contain exactly k distinct characters.

A substring is a contiguous sequence of characters within the string. The solution can be derived by leveraging the concept of counting substrings with at most k distinct characters. In particular, the answer is given by the formula:

$$ F(s, k) = A(s, k) - A(s, k-1) $$

where $$ A(s, k) $$ represents the number of substrings with at most k distinct characters.

Your program should read input from stdin and write the result to stdout.

inputFormat

The input consists of two lines:

1. The first line contains the string s (which may be empty).
2. The second line contains an integer k.

outputFormat

Output a single integer representing the number of substrings of s that contain exactly k distinct characters.

abac
2

4