Longest Substring with At Most K Distinct Characters

Given a string \(s\) and an integer \(k\), find the length of the longest substring of \(s\) that contains at most \(k\) distinct characters. In other words, if you slide a window over the string, determine the maximum window length such that the number of unique characters inside the window does not exceed \(k\). If \(k=0\), the answer is 0.

Example:

Input: s = "eceba", k = 2
Output: 3
Explanation: The substring "ece" contains 2 distinct characters and has a length of 3.

Use a sliding window technique (with two pointers) to efficiently maintain the count of distinct characters and update the answer. The core update is to calculate the window length using the formula: \(\text{length} = \text{right} - \text{left} + 1\).

inputFormat

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

• The first line contains the string \(s\), which is non-empty and may include any visible characters.
• The second line contains an integer \(k\) representing the maximum number of distinct characters allowed in the substring.

outputFormat

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

eceba
2

3