Longest Substring with At Most K Distinct Characters

Given a string \( S \) and an integer \( k \), your task is to determine the length of the longest contiguous substring of \( S \) that contains at most \( k \) distinct characters. For example, if \( S = \texttt{\"aabbcc\"} \) and \( k = 1 \), the answer is 2 because the longest substring containing only one distinct character is \( \texttt{\"aa\"} \) (or \( \texttt{\"bb\"} \) or \( \texttt{\"cc\"} \)).

The problem can be formally stated using the following formula:

[ \text{answer} = \max_{[i,j] \subseteq S} { j - i + 1 \mid \text{the substring } S[i\dots j] \text{ contains at most } k \text{ distinct characters} } ]

You need to implement an efficient solution which reads input data from standard input and writes the output to standard output.

inputFormat

The input consists of two lines:

• The first line contains the string \( S \). This string may include any printable characters.
• The second line contains a single integer \( k \), representing the maximum number of distinct characters allowed in the substring.

outputFormat

Output a single integer representing the length of the longest substring of \( S \) that contains at most \( k \) distinct characters.

aabbcc
1

2