Loading...
Loading...
Loading...
A music app logs the songs Rohit played in one evening, in order, as song codes. The app wants to find "focused" listening runs: runs of consecutive plays with exactly k different songs.
Print how many runs of consecutive plays have exactly k different song codes. Two runs are different if they start or end at a different play.
Example 1
Input
5 2 4 7 4 9 9
Output
5
Five runs have exactly two songs: 4 7, 4 7 4, 7 4, 4 9 and 4 9 9. The run 7 4 9 has three.
Example 2
Input
3 3 1 1 1
Output
0
There is only one different song, so no run has 3.
Try the problem first. Open one hint at a time.
Counting runs with at most k songs is easier: for each right, every start from left to right works, which is right - left + 1 runs.
Runs with exactly k songs = runs with at most k songs − runs with at most k − 1 songs.
Write one method atMost(k) with a moving left and a HashMap of song counts, and call it twice.
When all plays are the same song and n = 10^5, the answer is about 5 × 10^9, so keep the count in a long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor