Show problems as
Classic problem #2958MediumArrayHash TableSliding Window

Length of Longest Subarray With at Most K Frequency

Real-world version: Longest Stretch Under the Repeat Cap
Tracked in this browser only
Read Length of Longest Subarray With at Most K Frequency on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A support desk writes down the reason code attached to each ticket, in the order the tickets arrived, giving the list codes. Reviewers want to sample a block of consecutive tickets that is varied enough to be worth reading, so they allow a block only when no single reason code shows up in it more than cap times.

Return the number of tickets in the longest block of consecutive entries of codes in which every reason code appears at most cap times.

Examples

Example 1

Input
codes = [41, 52, 52, 63, 74, 85], cap = 1
Output
4

With a cap of one, the block of tickets 3 through 6 carries the codes 52, 63, 74 and 85, each once, so four tickets are allowed. Any block holding both copies of 52 breaks the cap.

Example 2

Input
codes = [6, 6, 2, 6, 2, 2, 9], cap = 2
Output
4

Tickets 3 through 6 read 2, 6, 2, 2, which holds code 2 three times, so that block is not allowed. Tickets 4 through 7 read 6, 2, 2, 9: code 2 appears twice and the others once, which is within the cap, giving a block of four.

Example 3

Input
codes = [7, 7, 7, 7], cap = 2
Output
2

Every ticket carries code 7, so a block of three would hold it three times. A block of two is the widest that stays within the cap.

Constraints

  • 1 <= codes.length <= 10^5
  • 1 <= codes[i] <= 10^9
  • 1 <= cap <= codes.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_capped_run(codes: list[int], cap: int) -> int:
Java
public int longestCappedRun(int[] codes, int cap)

More on the same topics