Longest Substring with At Most K Distinct Characters

You are given a string s and an integer k. Your task is to find the length of the longest substring of s that contains at most k distinct characters.

The problem can be solved efficiently using the sliding window technique. As you slide a window over the string, you maintain a count of distinct characters. If the count exceeds k, the window is moved forward until the condition is satisfied again. The maximal window size during this process is the answer.

Formally, given a string \( s \) and an integer \( k \), determine the maximum length \( L \) such that there exists a substring \( s[i \ldots j] \) with \( j - i + 1 = L \) where the number of distinct characters in the substring is \( \le k \).

Note: If k is 0 or if the string is empty, the answer is 0.

inputFormat

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

• The first line contains a non-empty string s (without spaces).
• The second line contains an integer k (\( k \ge 0 \)).

outputFormat

Output to stdout a single integer representing the length of the longest substring of s that contains at most k distinct characters.

abcba
2

3