Maximum Substring with K Distinct Characters

Given a string \(s\) consisting of only lowercase English letters and an integer \(k\), find the maximum length of a substring that contains at most \(k\) distinct characters.

More formally, for a given string \(s\) of length \(n\), determine the maximum integer \(L\) such that there exists an index pair \(i, j\) with \(0 \le i \le j < n\) where the substring \(s[i \ldots j]\) contains no more than \(k\) distinct characters and \(L = j - i + 1\). If \(k = 0\) or \(s\) is empty, the answer is 0.

Examples:

• For \(s = \texttt{\"eceba\"}\) and \(k = 2\), the answer is 3 (the substring \(\texttt{\"ece\"}\)).
• For \(s = \texttt{\"aa\"}\) and \(k = 1\), the answer is 2.

inputFormat

The input is given from standard input and consists of two lines:

1. The first line contains the string \(s\), which is a non-empty string of lowercase English letters. (It can be empty.)
2. The second line contains an integer \(k\) representing the maximum number of distinct characters allowed in a substring.

outputFormat

Output a single integer representing the maximum length of a substring of \(s\) that contains at most \(k\) distinct characters. The output should be written to standard output.

eceba
2

3