Longest Substring With At Most K Distinct Characters
Medium · sliding window
You are given a string s of lower case English letters and a whole number k.
A substring is a run of neighbouring characters of s. Look at all the substrings that contain at most k different letters, counting each letter once however many times it repeats. Return the length of the longest one.
If k is 0, no letter is allowed at all, so the answer is 0.
Examples
Example 1
Input: s = "abbcc", k = 2
Output: 4
The substring "bbcc" has only the letters b and c. Adding the a in front would make three letters.
Example 2
Input: s = "zzzz", k = 1
Output: 4
The whole string is one letter.
Example 3
Input: s = "abc", k = 0
Output: 0
No letters are allowed.
Constraints
- 1 <= len(s) <= 10^5
- s consists of lower case English letters
- 0 <= k <= 26