Longest Substring with At Most K Distinct Characters

Given a string \( s \) consisting of lowercase English letters and an integer \( k \), find the length of the longest substring of \( s \) that contains at most \( k \) distinct characters. In other words, if we denote by \( f(s, k) \) the maximum length of a contiguous segment in \( s \) such that the number of unique characters in that segment does not exceed \( k \), your task is to compute \( f(s, k) \).

Note: If \( k = 0 \), then the answer is \( 0 \) because no characters are allowed. Also, if \( k \) is greater than or equal to the number of distinct characters in \( s \), then the entire string is valid. This problem can be efficiently solved using the sliding window technique.

Example: For \( s = \texttt{eceba} \) and \( k = 2 \), one of the longest substrings with at most 2 distinct characters is \( \texttt{ece} \), so the answer is \( 3 \).

inputFormat

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

1. The first line contains the string \( s \), composed of lowercase English letters.
2. The second line contains a single integer \( k \), representing the maximum number of distinct characters allowed in the substring.

outputFormat

Output a single integer to standard output (stdout) which is the length of the longest substring of \( s \) that contains at most \( k \) distinct characters.

eceba
2

3