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 contiguous substring of \(S\) that contains at most \(K\) distinct characters.

Note: A substring is a contiguous sequence of characters within a string.

For example, if \(S = \texttt{ABBACAB}\) and \(K = 2\), the answer is \(4\) because the substring \(BBA\) or \(ACAB\) (among others) has at most 2 distinct characters and the maximum length is 4.

The problem requires efficient processing, so a two-pointer (sliding window) technique is recommended in order to achieve optimal time complexity.

inputFormat

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

• The first line contains a non-empty string \(S\) composed of uppercase English letters.
• The second line contains an integer \(K\) \( (0 \leq K \leq |S|) \) representing the maximum number of distinct characters allowed in the substring.

outputFormat

Output a single integer to stdout which is the length of the longest substring of \(S\) that contains at most \(K\) distinct characters.

ABBACAB
2

4