Loading...
Loading...
Loading...
A shop near the college sells name keychains. Its machine can hold metal blocks for at most k different letters at a time, but each letter can repeat any number of times.
The owner has a long text of lowercase letters. Find the length of the longest continuous piece of the text that uses at most k different letters.
Example 1
Input
eceba 2
Output
3
The piece ece uses only e and c, so the answer is 3.
Example 2
Input
aaaa 1
Output
4
The whole text uses one letter.
Try the problem first. Open one hint at a time.
Checking every piece separately is O(n²) or worse. Think about a piece that grows on the right and shrinks on the left.
Keep two ends, left and right. Add s[right] each step. When the piece has more than k different letters, move left forward.
Keep a count for each of the 26 letters inside the piece, and a counter of how many letters have a count above 0.
A letter leaves the piece only when its count drops to 0. Record the best length after the piece is valid again.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor