# Minimum Time to Remove All Cars Containing Illegal Goods
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-time-to-remove-all-cars-containing-illegal-goods)
Canonical: https://scaleengineer.com/dsa/problems/minimum-time-to-remove-all-cars-containing-illegal-goods
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## Problem
You are given a **0-indexed** binary string `s` which represents a sequence of train cars. `s[i] = '0'` denotes that the `ith` car does **not** contain illegal goods and `s[i] = '1'` denotes that the `ith` car does contain illegal goods.

As the train conductor, you would like to get rid of all the cars containing illegal goods. You can do any of the following three operations **any** number of times:

1. Remove a train car from the **left** end (i.e., remove `s[0]`) which takes 1 unit of time.
2. Remove a train car from the **right** end (i.e., remove `s[s.length - 1]`) which takes 1 unit of time.
3. Remove a train car from **anywhere** in the sequence which takes 2 units of time.

Return _the **minimum** time to remove all the cars containing illegal goods_.

Note that an empty sequence of cars is considered to have no cars containing illegal goods.

**Example 1:**

**Input:** s = "**11**00**1**0**1**"
**Output:** 5
**Explanation:** 
One way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the left end 2 times. Time taken is 2 * 1 = 2.
- remove a car from the right end. Time taken is 1.
- remove the car containing illegal goods found in the middle. Time taken is 2.
This obtains a total time of 2 + 1 + 2 = 5. 

An alternative way is to
- remove a car from the left end 2 times. Time taken is 2 * 1 = 2.
- remove a car from the right end 3 times. Time taken is 3 * 1 = 3.
This also obtains a total time of 2 + 3 = 5.

5 is the minimum time taken to remove all the cars containing illegal goods. 
There are no other ways to remove them with less time.

**Example 2:**

**Input:** s = "00**1**0"
**Output:** 2
**Explanation:**
One way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the left end 3 times. Time taken is 3 * 1 = 3.
This obtains a total time of 3.

Another way to remove all the cars containing illegal goods from the sequence is to
- remove the car containing illegal goods found in the middle. Time taken is 2.
This obtains a total time of 2.

Another way to remove all the cars containing illegal goods from the sequence is to 
- remove a car from the right end 2 times. Time taken is 2 * 1 = 2. 
This obtains a total time of 2.

2 is the minimum time taken to remove all the cars containing illegal goods. 
There are no other ways to remove them with less time.

**Constraints:**

* `1 <= s.length <= 2 * 105`
* `s[i]` is either `'0'` or `'1'`.

# Approaches
## Brute Force by Iterating All Middle Segments
This approach considers all possible ways to partition the removal operations. We can imagine that we remove a prefix, a suffix, and then handle the remaining middle part by removing each car with illegal goods individually. The total cost is the sum of costs for these three parts. We can iterate through all possible middle segments `s[i...j]`, calculate the cost for each, and find the minimum.
**Time:** O(n^2) due to the nested loops iterating through all possible start and end points of the middle segment. The precomputation of the prefix sum array takes O(n). · **Space:** O(n) to store the prefix sum array for counting ones.
**Pros:** The logic is relatively straightforward to understand as it directly models the partitioning of the string.; It correctly covers all possible scenarios of removals.
**Cons:** The time complexity of O(n^2) is too slow for the given constraints on the input size `s.length`, which can be up to 2 * 10^5. This will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The strategy is to define a segment `s[i...j]` of the train. All cars to the left of this segment, i.e., the prefix `s[0...i-1]`, are removed from the left end, costing `i` units of time. All cars to the right of this segment, i.e., the suffix `s[j+1...n-1]`, are removed from the right end, costing `n - (j+1)` units of time. All cars with illegal goods ('1's) within the segment `s[i...j]` are removed individually from the middle, costing `2` for each such car. The total cost for a chosen `i` and `j` is `i + (n - j - 1) + 2 * countOnes(s[i...j])`. We can iterate through all possible values of `i` (from `0` to `n`) and `j` (from `i-1` to `n-1`) to find the minimum possible total cost. To efficiently calculate `countOnes(s[i...j])`, we can precompute a prefix sum array that stores the cumulative count of '1's.

```java
class Solution {
    public int minimumTime(String s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }

        int[] prefixOnes = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixOnes[i + 1] = prefixOnes[i] + (s.charAt(i) - '0');
        }

        int minCost = Integer.MAX_VALUE;

        // i: start index of the middle segment
        // j: end index of the middle segment
        for (int i = 0; i <= n; i++) {
            for (int j = i - 1; j < n; j++) {
                int onesInMiddle = (j < i) ? 0 : prefixOnes[j + 1] - prefixOnes[i];
                // Cost = (remove prefix s[0..i-1]) + (remove suffix s[j+1..n-1]) + (remove middle '1's)
                int cost = i + (n - 1 - j) + 2 * onesInMiddle;
                minCost = Math.min(minCost, cost);
            }
        }
        return minCost;
    }
}
```
### Algorithm
*   To make the calculation of `countOnes(s[i...j])` efficient, first precompute a prefix sum array, `prefixOnes`, where `prefixOnes[k]` stores the total number of '1's in the prefix `s[0...k-1]`.
*   Initialize a variable `minCost` to a very large value.
*   Iterate through all possible start indices `i` of the middle segment, from `0` to `n`.
*   For each `i`, iterate through all possible end indices `j` of the middle segment, from `i-1` to `n-1`. The case `j = i-1` represents an empty middle segment.
*   Inside the loops, calculate the cost for the current partition `(i, j)`:
    *   Cost of removing the prefix `s[0...i-1]` is `i`.
    *   Cost of removing the suffix `s[j+1...n-1]` is `n - (j+1)`.
    *   Cost of removing '1's from the middle `s[i...j]` is `2 * (prefixOnes[j+1] - prefixOnes[i])`.
    *   The total cost is `i + (n - j - 1) + 2 * onesInMiddle`.
*   Update `minCost` with the minimum cost found so far.
*   After checking all `(i, j)` pairs, `minCost` will hold the result.

## Dynamic Programming with Prefix and Suffix Costs
This approach breaks the problem down by considering each position `i` as a potential split point. We calculate the minimum cost to clear all '1's to the left of `i` and the minimum cost to clear all '1's to the right of `i` (inclusive). The sum of these two costs gives a possible total minimum time. By checking every possible split point, we can find the global minimum.
**Time:** O(n), as it involves three separate linear passes: one to compute `left_costs`, one for `right_costs`, and one to combine them. · **Space:** O(n) to store the `left_costs` and `right_costs` arrays.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; The DP state transitions are simple and easy to implement once the subproblem structure is identified.
**Cons:** Requires O(n) extra space for the DP arrays, which might be a consideration for extremely large `n` under strict memory limits.; The logic, while efficient, might be less intuitive to come up with compared to a direct brute-force approach.
### Explanation
We can solve this problem efficiently using dynamic programming by splitting the problem at each possible index `i`. Let `left_costs[i]` be the minimum cost to remove all '1's in the prefix `s[0...i-1]`. This can be calculated by iterating from left to right. For each position `k < i`, if `s[k]` is a '1', we can either remove the whole prefix `s[0...k]` (cost `k+1`) or remove `s[k]` individually (cost 2) in addition to the cost of clearing `s[0...k-1]`. This gives a simple recurrence. Similarly, let `right_costs[i]` be the minimum cost to remove all '1's in the suffix `s[i...n-1]`, calculated by iterating from right to left.

The key insight is that for any split point `i`, the operations to clear the left part `s[0...i-1]` and the right part `s[i...n-1]` are independent. A left-end removal doesn't affect the right part, a right-end removal doesn't affect the left part, and middle removals are local. Therefore, the total minimum cost is the minimum of `left_costs[i] + right_costs[i]` over all possible split points `i`.

```java
class Solution {
    public int minimumTime(String s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }

        // left_costs[i] = min cost to clear '1's in s[0...i-1]
        int[] left_costs = new int[n + 1];
        left_costs[0] = 0;
        for (int i = 1; i <= n; i++) {
            if (s.charAt(i - 1) == '0') {
                left_costs[i] = left_costs[i - 1];
            } else {
                left_costs[i] = Math.min(left_costs[i - 1] + 2, i);
            }
        }

        // right_costs[i] = min cost to clear '1's in s[i...n-1]
        int[] right_costs = new int[n + 1];
        right_costs[n] = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                right_costs[i] = right_costs[i + 1];
            } else {
                right_costs[i] = Math.min(right_costs[i + 1] + 2, n - i);
            }
        }

        int minCost = Integer.MAX_VALUE;
        // Combine costs at each split point i
        for (int i = 0; i <= n; i++) {
            minCost = Math.min(minCost, left_costs[i] + right_costs[i]);
        }

        return minCost;
    }
}
```
### Algorithm
*   Create an array `left_costs` of size `n+1`. `left_costs[i]` will store the minimum cost to remove all '1's from the prefix `s[0...i-1]`.
*   Initialize `left_costs[0] = 0`.
*   Iterate `i` from 1 to `n` to fill `left_costs`. If `s[i-1] == '0'`, `left_costs[i] = left_costs[i-1]`. If `s[i-1] == '1'`, `left_costs[i] = min(left_costs[i-1] + 2, i)`. The two options correspond to removing `s[i-1]` from the middle or removing the entire prefix `s[0...i-1]`.
*   Create an array `right_costs` of size `n+1`. `right_costs[i]` will store the minimum cost to remove all '1's from the suffix `s[i...n-1]`.
*   Initialize `right_costs[n] = 0`.
*   Iterate `i` from `n-1` down to `0` to fill `right_costs`. If `s[i] == '0'`, `right_costs[i] = right_costs[i+1]`. If `s[i] == '1'`, `right_costs[i] = min(right_costs[i+1] + 2, n-i)`.
*   Initialize `minCost` to a large value.
*   The final answer is the minimum of `left_costs[i] + right_costs[i]` over all possible split points `i` from `0` to `n`.
*   Iterate `i` from `0` to `n`, updating `minCost = min(minCost, left_costs[i] + right_costs[i])`.
*   Return `minCost`.

# Solutions
### Java

```java
class Solution {
public
  int minimumTime(String s) {
    int n = s.length();
    int[] pre = new int[n + 1];
    int[] suf = new int[n + 1];
    for (int i = 0; i < n; ++i) {
      pre[i + 1] = s.charAt(i) == '0' ? pre[i] : Math.min(pre[i] + 2, i + 1);
    }
    for (int i = n - 1; i >= 0; --i) {
      suf[i] =
          s.charAt(i) == '0' ? suf[i + 1] : Math.min(suf[i + 1] + 2, n - i);
    }
    int ans = Integer.MAX_VALUE;
    for (int i = 1; i <= n; ++i) {
      ans = Math.min(ans, pre[i] + suf[i]);
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def minimumTime(self, s: str) -> int: n = len(s) pre = [0] * (n + 1) suf = [0] * (n + 1) for i, c in enumerate(s): pre[i + 1] = pre[i] if c == '0' else min(pre[i] + 2, i + 1) for i in range(n - 1, - 1, - 1): suf[i] = suf[i + 1] if s[i] == '0' else min(suf[i + 1] + 2, n - i) return min(a + b for a, b in zip(pre[1:], suf[1:]))

```

### CPP

```cpp
class Solution {
public:
  int minimumTime(string s) {
    int n = s.size();
    vector<int> pre(n + 1);
    vector<int> suf(n + 1);
    for (int i = 0; i < n; ++i)
      pre[i + 1] = s[i] == '0' ? pre[i] : min(pre[i] + 2, i + 1);
    for (int i = n - 1; ~i; --i)
      suf[i] = s[i] == '0' ? suf[i + 1] : min(suf[i + 1] + 2, n - i);
    int ans = INT_MAX;
    for (int i = 1; i <= n; ++i)
      ans = min(ans, pre[i] + suf[i]);
    return ans;
  }
};

```