Alternate After Rotating

Medium

You are given a string bits of zeros and ones. You may change it in two ways, in any order and as many times as you like: - **rotate**: take the first character off and append it to the end; this is free; - **flip**: replace any single character with the opposite one (0 with 1 or 1 with 0). A string is alternating if no two neighbouring characters are equal, like "1010" or "01010". Return the smallest number of flips needed to make the string alternating.

Example 1

bits="110" → 0

Moving the first character to the end gives "101", so no flips are needed.

Example 2

bits="0010" → 1

Flipping the first character gives "1010". Zero flips is impossible: an alternating string of length 4 has exactly two 1s.

Example 3

bits="11100" → 1

Constraints

1 ≤ len(bits) ≤ 10⁵
bits contains only the characters 0 and 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy String Dynamic Programming Sliding Window

Similar problems

Brackets With Wildcards Medium Bead String Without Twins Medium Hop Across Safe Tiles Medium Wells Beside the Houses Medium Binary Number Under a Cap Medium

Input

bits="110"

Expected

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