164. K Kinds of Letters
A paint shop receives a long strip of colored tape, described by the string s where each lowercase letter is one color. A customer wants a single continuous piece of the tape that uses at most k different colors, and wants that piece to be as long as possible.
Return the length of the longest contiguous substring of s that contains at most k distinct characters. If k is 0, no character is allowed, so the answer is 0. Letters may repeat any number of times inside the chosen piece; only the number of different letters is limited.
Example 1
- Input:
- s = "aabbcdd", k = 2
- Output:
- 4
- Explanation:
The substring "aabb" uses 2 colors and has length 4. Extending it by "c" would add a third color, and "cdd" has only length 3, so the best is 4.
Example 2
- Input:
- s = "zzzz", k = 3
- Output:
- 4
- Explanation:
The whole string uses a single color, which is within the limit of 3, so the answer is 4.
Example 3
- Input:
- s = "abc", k = 0
- Output:
- 0
- Explanation:
With k = 0 no letters are allowed at all, so the longest valid piece is empty and the answer is 0.
Constraints
1 ≤ s.length ≤ 105
s consists of lowercase English letters
0 ≤ k ≤ 26
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)