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.

Formally, if we denote a substring by s[i...j] (with 0 ≤ i ≤ j < n, where n is the length of s), find the maximum value of j - i + 1 such that the substring s[i...j] contains no more than k distinct characters.

Note that if k = 0 or if the string is empty, the answer is 0. You may assume that all characters in s are from the standard ASCII set.

The sliding window technique can be used to solve this problem efficiently in O(n) time, where n is the length of s. The idea is to maintain a window that keeps track of character frequencies and adjust its left boundary as soon as the count of distinct characters exceeds k.

Examples:

• For s = "eceba" and k = 2, the longest substring is "ece" with a length of 3.
• For s = "aa" and k = 1, the longest substring is "aa" with a length of 2.
• For s = "abcdeeecba" and k = 3, one valid substring is "cdeeec" having a length of 6.

The following formula summarizes the decision process in the sliding window approach:

$$\text{If }|Window| = j-i+1 \text{ and the window contains no more than } k \text{ distinct characters, then update } maxLength = \max(maxLength, j-i+1). $$

inputFormat

The input consists of two lines read from standard input:

1. A string s. This string may be empty.
2. An integer k (0 ≤ k ≤ |s|), representing the maximum number of distinct characters allowed in a substring.

Note: The string will be provided on the first line, and the integer on the second line.

outputFormat

Output a single integer: the length of the longest substring of s that contains at most k distinct characters. The result should be written to standard output.

## sample

eceba
2

3