Minimum time to remove all cars containing illegal goods

String Dynamic Programming

42.0% acceptance

Feb 25, 2026

703

You are given a 0-indexed binary string s. s[i] = '0' means car i has no illegal goods, s[i] = '1' means car i has illegal goods. You can: Remove a car from the left end (cost 1). Remove a car from the right end (cost 1). Remove a car from anywhere (cost 2). Return the minimum time to remove all cars containing illegal goods.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_time(s: String) -> i32 {
    let n = s.len();
    let bytes = s.as_bytes();

    // left[i] = min cost to remove all 1s in s[0..=i]
    let mut left = vec![0i32; n];
    if bytes[0] == b'1' {
      left[0] = 1;
    }
    for i in 1..n {
      left[i] = if bytes[i] == b'1' {
        (left[i - 1] + 2).min(i as i32 + 1)
      } else {
        left[i - 1]
      };
    }

    // right[i] = min cost to remove all 1s in s[i..n]
    let mut right = vec![0i32; n];
    if bytes[n - 1] == b'1' {
      right[n - 1] = 1;
    }
    for i in (0..n - 1).rev() {
      right[i] = if bytes[i] == b'1' {
        (right[i + 1] + 2).min((n - i) as i32)
      } else {
        right[i + 1]
      };
    }

    let mut ans = left[n - 1].min(right[0]);
    for i in 0..n - 1 {
      ans = ans.min(left[i] + right[i + 1]);
    }
    ans
  }
}