Longest Capped Window

Medium

You get an array values and an integer cap. A window of the array (one or more consecutive elements) is good if no value occurs in it more than cap times. Return the length of the longest good window.

Example 1

values=[4, 4, 1, 4, 2, 1, 1], cap=2 → 5

The window [4, 1, 4, 2, 1] has length 5 with two 4s and two 1s. Anything longer brings in a third 4 or a third 1.

Example 2

values=[3, 3, 3], cap=1 → 1

Each number may appear only once, so only a window of length 1 fits.

Example 3

values=[5, 6, 7, 5], cap=3 → 4

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁹
1 ≤ cap ≤ len(values)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Sliding Window

Similar problems

Two-Genre Stretch of a Playlist Medium Windows With an Exact Alarm Count Medium Stretches With k Odd Numbers Medium Two Separate Segments With a Given Sum Medium Trim the Ends to a Target Medium

Input

values=[4, 4, 1, 4, 2, 1, 1], cap=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 106 tests on the server, hidden ones included.