A street musician logs the id of every song she plays, in order, in songs. For a stretch of consecutive performances, a performance is an encore if the same song was already played earlier within that stretch. For example the stretch [4, 7, 4, 4] has 2 encores (the second and third 4).
Return the number of stretches (runs of consecutive performances, at least one long) that contain exactly k encores. Stretches at different positions count separately.
Examples
Input: songs = [4, 7, 4, 4, 2], k = 1
Output: 5
Explanation: [4, 7, 4], [7, 4, 4], [4, 4], [4, 4, 2] and [7, 4, 4, 2].
Input: songs = [1, 2, 3], k = 0
Output: 6
Explanation: no stretch repeats a song.
Input: songs = [5, 5, 5], k = 1
Output: 2
Constraints
0 <= len(songs) <= 10**50 <= k <= 10**50 <= songs[i] <= 10**9- Target complexity: O(n). Examining the stretches one by one (O(n²)) is too slow for the largest tests.
Goals
- Spot that the encore count never drops when a stretch is extended
- Count windows with an exact value as the difference of two 'at most' counts