Number of Substrings with Exactly K Distinct Characters

Number of Substrings with Exactly K Distinct Characters

Count substrings containing exactly K distinct characters using the at-most-K trick.

Input format

The first line contains a string S. The second line contains K.

Output format

Print the count of substrings with exactly K distinct characters.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

aaacb 3

3

aabab 3

0