All problems

Fresh Play Blocks

Medium · sliding window

A radio station keeps a log of the tracks it played, in order. The list plays holds one track number for each play, so the same number appears again every time that track is played.

A block is a run of exactly k plays in a row. A block is fresh if no single track is played more than t times inside it.

Return how many blocks of the log are fresh. Blocks that start at different positions are counted separately, even if they look the same.

Examples

Example 1

Input: plays = [1, 1, 2, 1, 3], k = 4, t = 2

Output: 1

There are two blocks of 4 plays. [1, 1, 2, 1] plays track 1 three times, which is more than 2, so it is not fresh. [1, 2, 1, 3] is fresh.

Example 2

Input: plays = [7, 7, 7, 7], k = 2, t = 1

Output: 0

Every block of 2 plays is two plays of track 7, and 2 is more than 1, so no block is fresh.

Example 3

Input: plays = [4, 5, 4, 4, 6, 5], k = 4, t = 2

Output: 2

There are three blocks. [4, 5, 4, 4] plays track 4 three times, so it is not fresh. [5, 4, 4, 6] and [4, 4, 6, 5] are fresh.

Constraints