Setlist Genre Stretch
Medium · sliding window
A street musician plans an evening on a busy corner. The list setlist holds the songs she will play, in order. Each value is the genre of that song, written as a whole number, so two songs with the same number belong to the same genre.
Her amp only has room for k different genre cards, so she looks for a stretch of songs in a row, with none skipped, that uses at most k different genres.
Return [start, length] for the longest such stretch: start is the position of its first song (counting from 0) and length is how many songs it holds. If several stretches are equally long, return the one with the smallest start.
Examples
Example 1
Input: setlist = [1, 2, 1, 3, 3, 2, 2], k = 2
Output: [3, 4]
Positions 3 to 6 hold genres 3, 3, 2, 2. Positions 0 to 2 only reach three songs, and no stretch of five songs has two genres or fewer.
Example 2
Input: setlist = [5, 5, 6], k = 1
Output: [0, 2]
Example 3
Input: setlist = [4], k = 3
Output: [0, 1]
Constraints
- 1 <= len(setlist) <= 10^5
- 1 <= k <= 10^5
- 0 <= setlist[i] <= 10^9