Show problems as
Classic problem #424MediumHash TableStringSliding Window

Longest Repeating Character Replacement

Real-world version: Longest Repainted Stretch
Tracked in this browser only
Read Longest Repeating Character Replacement on LeetCode(opens in a new tab)

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

Learn the pattern firstSliding Window · Strings, animated step by step

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 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_uniform_run(panels: str, budget: int) -> int:
Java
public int longestUniformRun(String panels, int budget)

More on the same topics