0238MediumStringDynamic ProgrammingSliding Window

Repaint the Calibration Band

Tracked in this browser only

Trains the technique from

LeetCode 1888Minimum Number of Flips to Make the Binary String Alternating

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 calibration band is a closed loop of printed cells wrapped around a drum. Each cell carries either '0' or '1'. The reader makes one full pass over the loop, starting at the cell sitting under the head mark, and writes what it saw as the string band.

Before the drum is certified you may use these two adjustments, in any order and as often as you like:

Advance the drum by one cell. The cell under the head mark moves to the tail of the pass and every remaining cell moves one place earlier. Advancing is free.
Repaint one cell, turning its '0' into '1' or its '1' into '0'. Each repaint costs one unit.

The drum is certified once no two neighbouring cells of the pass carry the same character.

Return the smallest total repaint cost that certifies the drum.

Examples

Example 1

Input: band = "1100011"
Output: 2

Advancing the drum once makes the pass `1000111`. Repainting its third and sixth cells leaves `1010101`, where no two neighbours carry the same character, for a cost of 2.

Example 2

Input: band = "0110101"
Output: 0

Advancing the drum twice makes the pass `1010101`, whose neighbours already differ everywhere, so nothing is repainted.

Example 3

Input: band = "1111"
Output: 2

Repainting the first and third cells leaves the pass `0101`, where no two neighbours carry the same character, for a cost of 2.

Constraints

1 <= band.length <= 10^5
band[i] is either '0' or '1'

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 min_repaint_cost(band: str) -> int:

Java

public int minRepaintCost(String band)

The intended approach

Time O(n)Space O(1)

Advancing the drum k times yields the pass that begins at cell k, so the candidate passes are the n cyclic windows of length n over the band. A certified pass of length n is one of exactly two strings, decided by the character it opens with, and those two are complements of each other, so a window that mismatches one of them in c places mismatches the other in n - c places. The loop walks 2n indices while holding the mismatch count of the current window against the pattern anchored to absolute index parity, adding the entering cell and subtracting the leaving cell, and keeps the smallest of c and n - c seen over all windows. Indexing modulo n means the doubled band is never built.

Pythonentry point: min_repaint_cost

def min_repaint_cost(band):
    n = len(band)
    mismatch = 0
    best = n
    for i in range(2 * n):
        wanted = "0" if i % 2 == 0 else "1"
        if band[i % n] != wanted:
            mismatch += 1
        if i >= n:
            out = i - n
            leaving = "0" if out % 2 == 0 else "1"
            if band[out] != leaving:
                mismatch -= 1
        if i >= n - 1:
            if mismatch < best:
                best = mismatch
            if n - mismatch < best:
                best = n - mismatch
    return best

The obvious version

Materialise every one of the n possible passes, score each against both certified strings of that length by walking it cell by cell, and keep the cheapest score. 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_min_repaint_cost(band):
    n = len(band)
    best = n
    for turns in range(n):
        pass_read = band[turns:] + band[:turns]
        for opener in ("0", "1"):
            cost = 0
            wanted = opener
            for cell in pass_read:
                if cell != wanted:
                    cost += 1
                wanted = "1" if wanted == "0" else "0"
            if cost < best:
                best = cost
    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