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 substring of s that contains at most k distinct characters.

The problem can be formalized using the following formula. Let f(l, r) be the number of distinct characters in the substring s[l...r]. We want to find the maximum value of (r - l + 1) such that:

\( f(l, r) \le k \)

If k = 0, then the answer is 0.

Examples:

• For s = "abcba" and k = 2, the result is 3.
• For s = "aaabbcc" and k = 2, the result is 5.

inputFormat

The input is given via standard input (stdin) and consists of two lines. The first line contains a non-empty string s consisting of lowercase letters. The second line contains a non-negative integer k.

outputFormat

Output one integer: the length of the longest substring of s that contains at most k distinct characters. If k equals 0, output 0.

abcba
2

3