0651MediumArrayHash TableSliding Window

Longest Stretch Under the Repeat Cap

Tracked in this browser only

Trains the technique from

LeetCode 2958Length of Longest Subarray With at Most K Frequency

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def longest_capped_run(codes: list[int], cap: int) -> int:

Java

public int longestCappedRun(int[] codes, int cap)

The intended approach

Time O(n): each edge of the window moves forward at most n times.Space O(n) for the tally, which can hold every distinct code in the window.

Hold a window over the list with a tally of how often each reason code appears inside it. Extend the right edge one ticket at a time; the only code that can have broken the cap is the one just added, so keep pulling tickets off the left edge and lowering their tallies until that code is back within the cap. The window is always allowed after that trim, so its width is a candidate answer.

Pythonentry point: longest_capped_run

def longest_capped_run(codes, cap):
    # Grow the window on the right; while the code just added breaks the cap,
    # drop codes off the left. O(n) time, O(n) space for the tally.
    tally = {}
    left = 0
    best = 0
    for right in range(len(codes)):
        c = codes[right]
        tally[c] = tally.get(c, 0) + 1
        while tally[c] > cap:
            tally[codes[left]] -= 1
            left += 1
        if right - left + 1 > best:
            best = right - left + 1
    return best

The obvious version

Start a block at every position and extend it one ticket at a time, tallying as you go. Stop that block as soon as some code exceeds the cap, and remember the widest block seen.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_longest_capped_run(codes, cap):
    n = len(codes)
    best = 0
    for i in range(n):
        tally = {}
        for j in range(i, n):
            tally[codes[j]] = tally.get(codes[j], 0) + 1
            if tally[codes[j]] > cap:
                break
            if j - i + 1 > best:
                best = j - i + 1
    return best

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in