Even Blocks in a Bit String

Medium

You get a string bits of even length made of 0 and 1. Call a string tidy if it can be cut into pieces so that every piece has even length and consists of a single repeated symbol (all zeros or all ones). One fix flips any single character. Return the minimum number of fixes that makes bits tidy.

Example 1

bits="0110" → 2

Both pairs "01" and "10" are mixed, so each needs one change, giving e.g. "0000". Total 2.

Example 2

bits="110000" → 0

The string already splits into "11" and "0000", so nothing needs changing.

Example 3

bits="01" → 1

Constraints

2 ≤ len(bits) ≤ 10⁵
len(bits) is even
bits contains only 0 and 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String

Similar problems

Longest Repeat-Free Stretch Medium Longest Mirror Fragment Medium Reading a Zigzag by Rows Medium Lenient Number Reader Medium Number in Roman Numerals Medium

Input

bits="0110"

Expected

Run checks the first 3 tests in your browser. Submit checks all 119 tests on the server, hidden ones included.