Count Distinct Substrings with At Most K Distinct Characters

You are given a non-empty string s and an integer k. Your task is to count the number of distinct non-empty substrings of s that contain at most k distinct characters.

A substring is a contiguous sequence of characters within a string. Two substrings are considered distinct if they differ in content. For example, in the string abcba with k = 2, the distinct substrings that meet the condition are counted and the total is 8.

Note: If a substring contains more than k distinct characters, it should not be counted.

The solution may involve iterating over all possible substrings (using a double loop) and maintaining a set of unique characters. An efficient implementation is expected to handle the given input sizes.

Mathematical Formulation: Let \( S \) be the set of all non-empty substrings of s. Define a function \( f(t) \) that returns 1 if the substring \( t \) contains at most \( k \) distinct characters, and 0 otherwise. The answer is given by:

[ \text{Answer} = \sum_{t \in S} f(t) \quad \text{where} \quad f(t) = \begin{cases} 1, & \text{if } #{\text{distinct characters in } t} \le k \ 0, & \text{otherwise} \end{cases} ]

inputFormat

The input will be provided via standard input (stdin) and consists of two tokens separated by whitespace:

• A string s (containing only printable characters and no spaces).
• An integer k indicating the maximum number of distinct characters allowed in a substring.

Input example (on separate lines):

abcba
2

outputFormat

Output a single integer on standard output (stdout) representing the number of distinct non-empty substrings of s that contain at most k distinct characters.

Output example:

8

## sample

abcba
2

8