Flip String to Monotone Increasing

Medium Topics Company Tags

Change any bit of s in one operation. Return the fewest changes needed to obtain a string consisting of zero or more 0 characters followed by zero or more 1 characters.

Example 1:

Input: s = "1100"

Output: 2

Explanation: Flip the first two bits to get "0000", or the last two to get "1111". A single flip cannot remove every 1-before-0 violation.

Example 2:

Input: s = "0000"

Output: 0

Explanation: All bits are 0, which is already a valid monotone string with no trailing ones.

Example 3:

Input: s = "1111"

Output: 0

Explanation: All bits are 1, which is already a valid monotone string with no leading zeros.

Constraints:

  • 1 <= s.length <= 100000
  • Each character is 0 or 1.


Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.