#633 · Sliding window · Advanced · Fast enough · 115 XP · about 20 min
An ice cream shop features one flavor each day, and flavors lists the flavor codes in order: flavors[0] was featured on day 0. For an ad the shop wants the run of k days in a row that featured the most different flavors.
Write most_varied(flavors, k) that returns a tuple (count, start): the largest number of different flavors in any k consecutive days, and the first day of the earliest run that has that many.
most_varied([1, 2, 1, 3, 4, 4, 2], 3) # returns (3, 1) most_varied([5, 5, 5], 2) # returns (1, 0) most_varied([7, 8, 9], 3) # returns (3, 0)
In the first example the three-day runs hold 2, 3, 3, 2 and 2 different flavors. Days 1 to 3 and days 2 to 4 both have 3, and the earlier run starts on day 1.
1 <= k <= len(flavors) <= 200,000Each test must finish within 10 seconds, and the hidden tests have 200,000 days with runs tens of thousands of days long.
First solves only, ranked by stars and then time.