Flip string to monotone increasing

String Dynamic Programming

61.9% acceptance

Feb 25, 2026

4582

185

A binary string is monotone increasing if it consists of some number of 0's (possibly none), followed by some number of 1's (also possibly none). You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0. Return the minimum number of flips to make s monotone increasing.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_flips_mono_incr(s: String) -> i32 {
    // dp: flips keeping everything up to index as valid monotone
    // ones = number of 1s seen so far (flipping them to 0 to extend the 0-prefix)
    // flips = min flips to make s[0..i] monotone increasing
    let mut ones = 0i32;
    let mut flips = 0i32;
    for c in s.chars() {
      if c == '1' {
        ones += 1;
        // don't flip this 1
      } else {
        // either flip this 0 to 1 (cost 1), or flip all previous 1s to 0
        flips = (flips + 1).min(ones);
      }
    }
    flips
  }
}