Repaint the Fence

Mediumsliding windowAlso known as Longest Repeating Character Replacement

A long garden fence is made of boards that neighbours have painted over the years in different colours. Each board's colour is a capital letter, so the fence reads like "GGRGBBG".

An artist wants an unbroken stretch of boards in one single colour as the background for a mural. She only has enough paint for k boards. Repainting a board changes it to any colour she likes. What is the longest one-colour stretch she can end up with?

Your task

Write longestOneColour(boards, k). You may change at most k characters of boards, each to any capital letter. Return the length of the longest run of consecutive equal characters you can make.

An empty fence gives 0.

longestOneColour(boards: string, k: int) → int

Examples

Example 1

Input

boards = "GGRGBBG"
k = 1

Output

Why

Repaint the R green: the first four boards become GGGG. That uses the one repaint. The stretch GGRGB would need two repaints (the R and the B), which is too many. The answer is 4.

Example 2

Input

boards = "RBRBRB"
k = 2

Output

Why

Take the five boards RBRBR. Repainting the two B's red makes RRRRR, length 5. Every 6-board stretch has three of each colour, so it would need three repaints.

Constraints

0 ≤ boards.length ≤ 10,000
0 ≤ k ≤ boards.length
boards contains capital letters A-Z only.

Start with brute force

Check every stretch: for each start and end, count the colours, and if length - mostCommon ≤ k, record the length.

There are about 50 million stretches in a 10,000-board fence, and each needs its own counts. Even with counts updated as the end moves, it is O(n²) work, and most stretches are obviously too short or obviously too expensive.

Hints

0 of 4 shown

Hint 1
Pick any stretch of boards, like GGRGB. How many repaints does it take to make it all one colour, and which colour should you choose?
Hint 2
Keep the colour that already appears most in the stretch and repaint the rest. So a stretch is possible when length - (count of its most common colour) ≤ k.
Hint 3
That rule lets you use a window. Grow it on the right. When it needs more than k repaints, slide the left edge forward by one board.
Hint 4
Keep counts of each colour in the window and the highest count seen so far, top. For each right: count the new board and update top. While windowLength - top > k, remove the left board from the counts and move left. Record the window length. (top never needs to go down: a smaller top can never beat the best length you already found.)

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

A stretch can be made one colour with length - mostCommon repaints: keep the commonest colour and repaint the others. So slide a window and keep it within budget.

Trace "GGRGBBG" with k = 1:

Add G, G: window GG, top 2, repaints 0. Best 2.
Add R: GGR, top 2, repaints 1. Best 3.
Add G: GGRG, top 3, repaints 1. Best 4.
Add B: GGRGB, top 3, repaints 2. Too many. Drop the left G: GRGB, length 4, repaints 4 - 3 = 1 by the rule. Best stays 4.
Add B: length 5, repaints 2. Drop G: RGBB, length 4. Best stays 4.
Add G: length 5, repaints 2. Drop R: GBBG, length 4. Best stays 4.

Look at steps 4 to 6. top stayed 3 after G's left the window, so the code thinks GRGB needs 1 repaint when it really needs 2. That is safe, for two reasons.

First, with a stale top the window only slides at its current size, which is a length you already proved possible earlier. It never records a longer one. Second, the window can only grow past that size when a new board pushes top higher. At that moment top is the real count of the board just added, inside the current window, so the longer window really is possible. A lower top could only describe shorter stretches, and those can never beat best.

Reference solution

function longestOneColour(boards, k) {
  const count = new Map(); // colour -> boards in the window
  let left = 0, top = 0, best = 0;
  for (let right = 0; right < boards.length; right++) {
    const c = boards[right];
    count.set(c, (count.get(c) || 0) + 1);
    top = Math.max(top, count.get(c));
    // Too many repaints needed: drop the leftmost board.
    while (right - left + 1 - top > k) {
      count.set(boards[left], count.get(boards[left]) - 1);
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

def longest_one_colour(boards, k):
    count = {}  # colour -> boards in the window
    left = top = best = 0
    for right, c in enumerate(boards):
        count[c] = count.get(c, 0) + 1
        top = max(top, count[c])
        # Too many repaints needed: drop the leftmost board.
        while right - left + 1 - top > k:
            count[boards[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

TimeO(n)Each board enters the window once and leaves at most once; counting is O(1).

SpaceO(1)At most 26 colour counts.

Learn the idea: Sliding Window Hash Tables Strings

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code