Zeros First, Then Ones

Medium

A sensor recorded a string bits of 0 and 1 characters. The signal is supposed to be a single step: only zeros first, then only ones (either part may be empty). One fix flips any single character to the other value. Return the smallest number of fixes that turns the string into such a step.

Example 1

bits='010110' → 2

Two fixes are enough: change the 1 at index 1 to 0 and the 0 at index 5 to 1, giving 000111.

Example 2

bits='1100' → 2

Either clear both ones (0000) or set both zeros (1111); either way it takes two fixes.

Example 3

bits='0011' → 0

The string is already in order, so nothing needs fixing.

Constraints

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

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Longest Mirror Fragment Medium All Balanced Bracket Strings Medium Fewest Letter Edits Medium Ways to Read a Digit Code Medium Weaving Two Strings Medium

Input

bits='010110'

Expected

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