A radio station wants to check how varied its playlist feels. playlist[i] is the artist of the i-th song. For every stretch of k consecutive songs, count how many artists appear two or more times in that stretch.
Write repeat_artists(playlist: list[str], k: int) -> list[int] returning one count per stretch, left to right (stretch i covers playlist[i:i + k], so there are len(playlist) - k + 1 of them).
repeat_artists(["abba", "cher", "abba", "cher", "dido", "abba"], 4)
# [2, 1, 1]
# [abba cher abba cher] -> abba and cher repeat -> 2
# [cher abba cher dido] -> cher repeats -> 1
# [abba cher dido abba] -> abba repeats -> 1
repeat_artists(["x", "x", "x"], 2) # [1, 1] an artist counts once, however often they repeat
1 <= k <= len(playlist) <= 2 * 10^5; artist names are non-empty strings.- Rebuilding a
Counterfor each stretch is O(n·k). The tests includen = 200,000withk = 20,000, where that takes far too long. Aim for O(n).
Show hint
keep a dict of counts for the current stretch plus a running number repeats of artists whose count is at least 2; when a song enters and its artist's count goes from 1 to 2, repeats += 1, and when a song leaves and its artist's count drops from 2 to 1, repeats -= 1.