Swaps to a Zebra String

Medium

You get a string bits made of 0 and 1. Call it a zebra if no two neighboring characters are equal: for example, 0101 and 101 are zebras while 0110 is not. In one move you may swap any two characters of the string, not necessarily adjacent ones. Return the fewest moves that turn bits into a zebra, or -1 if that is impossible.

Example 1

bits="0011" → 1

Swap the characters at indices 1 and 2 to get 0101.

Example 2

bits="10101" → 0

The string already alternates.

Example 3

bits="0001" → -1

There are two more zeros than ones, so no alternating order exists.

Constraints

1 ≤ len(bits) ≤ 10⁵
bits consists only of 0 and 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy String

Similar problems

Biggest Number From Pieces Medium Every Letter Once Medium Erase Digits for the Smallest Number Medium Smallest Up-Down Sequence Medium Ring of Flippable Words Medium

Input

bits="0011"

Expected

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