Show problems as
Classic problem #1888MediumStringDynamic ProgrammingSliding Window

Minimum Number of Flips to Make the Binary String Alternating

Real-world version: Repaint the Calibration Band
Tracked in this browser only
Read Minimum Number of Flips to Make the Binary String Alternating on LeetCode(opens in a new tab)

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

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

Python
def min_repaint_cost(band: str) -> int:
Java
public int minRepaintCost(String band)

More on the same topics