Minimum flips to make binary string coherent

18.7% acceptance

May 13, 2026

You are given a binary string s. A string is considered coherent if it does not contain "011" or "110" as subsequences. In one operation, you can flip any character in s ('0' to '1' or '1' to '0'). Return an integer denoting the minimum number of modifications required to make s coherent. A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_flips(s: String) -> i32 {
    let bytes: Vec<u8> = s.bytes().map(|b| b - b'0').collect();
    let n = bytes.len();
    let cnt1: i32 = bytes.iter().map(|&x| x as i32).sum();
    let cnt0 = n as i32 - cnt1;
    let mut best = cnt1.min(cnt0);
    let max_s = bytes.iter().max().copied().unwrap_or(0) as i32;
    let single_one_cost = 1 + cnt1 - 2 * max_s;
    best = best.min(single_one_cost);
    if n >= 3 {
      let mid_ones: i32 = bytes[1..n - 1].iter().map(|&x| x as i32).sum();
      let cost = (1 - bytes[0] as i32) + (1 - bytes[n - 1] as i32) + mid_ones;
      best = best.min(cost);
    }
    best
  }
}