0033MediumHash TableStringSliding Window

Longest Repainted Stretch

Tracked in this browser only

Trains the technique from

LeetCode 424Longest Repeating Character Replacement

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 contractor is freshening up a fence. panels is a string of uppercase letters read left to right, one letter per panel, naming the colour that panel carries today. There is enough paint on the truck to recoat at most budget panels, and a recoated panel may be given whichever colour the contractor likes.

Report the greatest number of neighbouring panels that can end up sharing a single colour once at most budget of them have been recoated. Leftover paint may go unused, and the panels chosen for recoating need not sit next to one another.

Examples

Example 1

Input: panels = "GHGGHHHG", budget = 1
Output: 4

Recoating the G at position 3 leaves positions 3 through 6 all showing H, a stretch of 4. No stretch of 5 can be evened out with a single recoat.

Example 2

Input: panels = "KKLLMM", budget = 1
Output: 3

Every stretch of 4 here holds two colours in equal share, so it would need two recoats. Recoating the L at position 2 gives three consecutive K panels.

Example 3

Input: panels = "GGGG", budget = 2
Output: 4

The fence is already one colour, so the whole run of 4 qualifies and the paint stays on the truck.

Constraints

1 <= panels.length <= 10^5
panels consists of uppercase English letters only.
0 <= budget <= panels.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_uniform_run(panels: str, budget: int) -> int:

Java

public int longestUniformRun(String panels, int budget)

The intended approach

Time O(26 * n)Space O(1), a fixed tally of 26 colours

Slide a window and keep a tally of how many panels of each colour sit inside it. A window is affordable when its width minus the tally of its most common colour is within budget, since every other panel has to be recoated to that colour. Extend the right edge one panel at a time and pull the left edge forward while the window is unaffordable; the widest affordable window seen is the answer.

Pythonentry point: longest_uniform_run

def longest_uniform_run(panels, budget):
    tally = [0] * 26
    left = 0
    best = 0
    for right in range(len(panels)):
        tally[ord(panels[right]) - 65] += 1
        while (right - left + 1) - max(tally) > budget:
            tally[ord(panels[left]) - 65] -= 1
            left += 1
        width = right - left + 1
        if width > best:
            best = width
    return best

The obvious version

Take every start position, grow the stretch one panel at a time while tallying colours, and keep the widest stretch whose non-dominant panels fit inside the budget. O(n^2).

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_uniform_run(panels, budget):
    n = len(panels)
    best = 0
    for start in range(n):
        tally = {}
        for end in range(start, n):
            colour = panels[end]
            tally[colour] = tally.get(colour, 0) + 1
            width = end - start + 1
            if width - max(tally.values()) <= budget and width > best:
                best = width
    return best

How this problem was checked

Reference solution executed against 13 test cases — 13 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