Longest Substring with at Most K Distinct Characters
mediumStrings II+20 XPTime limit 2s
A fruit stall records the fruits it sells through the day as a string of letters. Find the length of the longest stretch (a contiguous substring) that contains at most k different letters. In eceba with k = 2, the longest such stretch is ece — length 3.
Input:
- line 1: the string (lowercase letters)
- line 2:
k
Output: the length of the longest substring with at most k distinct characters.
Constraints: 1 ≤ length ≤ 10⁵, 1 ≤ k ≤ 26.
Think about it: sliding window. Extend the right end one character at a time and count characters inside the window. When the window has more than k distinct characters, move the left end forward (decreasing counts, dropping letters that reach 0) until it is valid again. Record the best window size.
Sample input 1
eceba 2
Sample output 1
3
Sample input 2
aa 1
Sample output 2
2
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).