Toggle to the End of the Row

Medium

A row of n bulbs starts with every bulb off. The string pattern of length n, made of 0 and 1, shows the state you want: 1 means on, 0 means off. In one step you pick a position i and toggle every bulb from i to the end of the row: bulbs that are on go off and bulbs that are off light up. Return the smallest number of steps after which the row matches pattern.

Example 1

pattern="0110" → 2

Toggle from position 1: "0000" → "0111", then from position 3: "0111" → "0110". Two steps.

Example 2

pattern="1010" → 4

Every position differs from the one before it, so each needs its own step: 4.

Example 3

pattern="000" → 0

The row already matches the pattern, so nothing needs to be done.

Constraints

1 ≤ len(pattern) ≤ 10⁵
pattern consists of the characters 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

pattern="0110"

Expected

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