Time needed to rearrange a binary string

String Dynamic Programming Simulation

52.6% acceptance

Feb 25, 2026

550

116

You are given a binary string s. In one second, all occurrences of "01" are simultaneously replaced with "10". This process repeats until no occurrences of "01" exist. Return the number of seconds needed to complete this process.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn seconds_to_remove_occurrences(s: String) -> i32 {
    let mut chars: Vec<u8> = s.bytes().collect();
    let n = chars.len();
    let mut t = 0;
    loop {
      let v = chars.clone();
      let mut changed = false;
      for i in 0..n-1 {
        if v[i] == b'0' && v[i+1] == b'1' {
          chars[i] = b'1';
          chars[i+1] = b'0';
          changed = true;
        }
      }
      if !changed { break; }
      t += 1;
    }
    t
  }
}