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 theminimum 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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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 * 10^5
  • s[i] is either '0' or '1'.

Solution

Method 1 – Dynamic Programming (Prefix and Suffix Minimums)

Intuition

We can remove cars from the left, right, or anywhere (with different costs). For each position, we can compute the minimum cost to remove all illegal cars to the left and right, and combine them for the optimal solution.

Approach

  1. Let n = length of s.
  2. Create prefix and suffix arrays:
    • prefix[i]: minimum time to remove all illegal cars from s[0..i].
    • suffix[i]: minimum time to remove all illegal cars from s[i..n-1].
  3. For prefix:
    • If s[i] == ‘0’, prefix[i] = prefix[i-1].
    • If s[i] == ‘1’, prefix[i] = min(prefix[i-1] + 1, i + 1).
  4. For suffix:
    • If s[i] == ‘0’, suffix[i] = suffix[i+1].
    • If s[i] == ‘1’, suffix[i] = min(suffix[i+1] + 1, n - i).
  5. The answer is min(prefix[i] + suffix[i+1]) for all i.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    int minimumTime(string s) {
        int n = s.size();
        vector<int> pre(n), suf(n);
        pre[0] = s[0] == '1' ? 1 : 0;
        for (int i = 1; i < n; ++i) {
            if (s[i] == '1')
                pre[i] = min(pre[i-1] + 1, i + 1);
            else
                pre[i] = pre[i-1];
        }
        suf[n-1] = s[n-1] == '1' ? 1 : 0;
        for (int i = n-2; i >= 0; --i) {
            if (s[i] == '1')
                suf[i] = min(suf[i+1] + 1, n - i);
            else
                suf[i] = suf[i+1];
        }
        int ans = suf[0];
        for (int i = 0; i < n-1; ++i)
            ans = min(ans, pre[i] + suf[i+1]);
        ans = min(ans, pre[n-1]);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

func minimumTime(s string) int {
    n := len(s)
    pre := make([]int, n)
    suf := make([]int, n)
    if s[0] == '1' {
        pre[0] = 1
    }
    for i := 1; i < n; i++ {
        if s[i] == '1' {
            pre[i] = min(pre[i-1]+1, i+1)
        } else {
            pre[i] = pre[i-1]
        }
    }
    if s[n-1] == '1' {
        suf[n-1] = 1
    }
    for i := n-2; i >= 0; i-- {
        if s[i] == '1' {
            suf[i] = min(suf[i+1]+1, n-i)
        } else {
            suf[i] = suf[i+1]
        }
    }
    ans := suf[0]
    for i := 0; i < n-1; i++ {
        ans = min(ans, pre[i]+suf[i+1])
    }
    ans = min(ans, pre[n-1])
    return ans
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int minimumTime(String s) {
        int n = s.length();
        int[] pre = new int[n], suf = new int[n];
        pre[0] = s.charAt(0) == '1' ? 1 : 0;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == '1')
                pre[i] = Math.min(pre[i-1] + 1, i + 1);
            else
                pre[i] = pre[i-1];
        }
        suf[n-1] = s.charAt(n-1) == '1' ? 1 : 0;
        for (int i = n-2; i >= 0; i--) {
            if (s.charAt(i) == '1')
                suf[i] = Math.min(suf[i+1] + 1, n - i);
            else
                suf[i] = suf[i+1];
        }
        int ans = suf[0];
        for (int i = 0; i < n-1; i++)
            ans = Math.min(ans, pre[i] + suf[i+1]);
        ans = Math.min(ans, pre[n-1]);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun minimumTime(s: String): Int {
        val n = s.length
        val pre = IntArray(n)
        val suf = IntArray(n)
        pre[0] = if (s[0] == '1') 1 else 0
        for (i in 1 until n) {
            pre[i] = if (s[i] == '1') minOf(pre[i-1]+1, i+1) else pre[i-1]
        }
        suf[n-1] = if (s[n-1] == '1') 1 else 0
        for (i in n-2 downTo 0) {
            suf[i] = if (s[i] == '1') minOf(suf[i+1]+1, n-i) else suf[i+1]
        }
        var ans = suf[0]
        for (i in 0 until n-1) {
            ans = minOf(ans, pre[i]+suf[i+1])
        }
        ans = minOf(ans, pre[n-1])
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def minimumTime(self, s: str) -> int:
        n: int = len(s)
        pre: list[int] = [0] * n
        suf: list[int] = [0] * n
        pre[0] = 1 if s[0] == '1' else 0
        for i in range(1, n):
            if s[i] == '1':
                pre[i] = min(pre[i-1]+1, i+1)
            else:
                pre[i] = pre[i-1]
        suf[n-1] = 1 if s[n-1] == '1' else 0
        for i in range(n-2, -1, -1):
            if s[i] == '1':
                suf[i] = min(suf[i+1]+1, n-i)
            else:
                suf[i] = suf[i+1]
        ans: int = suf[0]
        for i in range(n-1):
            ans = min(ans, pre[i]+suf[i+1])
        ans = min(ans, pre[n-1])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn minimum_time(s: String) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let mut pre = vec![0; n];
        let mut suf = vec![0; n];
        pre[0] = if s[0] == b'1' { 1 } else { 0 };
        for i in 1..n {
            pre[i] = if s[i] == b'1' { pre[i-1]+1 }.min(i+1) else { pre[i-1] };
        }
        suf[n-1] = if s[n-1] == b'1' { 1 } else { 0 };
        for i in (0..n-1).rev() {
            suf[i] = if s[i] == b'1' { suf[i+1]+1 }.min(n-i) else { suf[i+1] };
        }
        let mut ans = suf[0];
        for i in 0..n-1 {
            ans = ans.min(pre[i]+suf[i+1]);
        }
        ans = ans.min(pre[n-1]);
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    minimumTime(s: string): number {
        const n = s.length;
        const pre = Array(n).fill(0);
        const suf = Array(n).fill(0);
        pre[0] = s[0] === '1' ? 1 : 0;
        for (let i = 1; i < n; i++) {
            pre[i] = s[i] === '1' ? Math.min(pre[i-1]+1, i+1) : pre[i-1];
        }
        suf[n-1] = s[n-1] === '1' ? 1 : 0;
        for (let i = n-2; i >= 0; i--) {
            suf[i] = s[i] === '1' ? Math.min(suf[i+1]+1, n-i) : suf[i+1];
        }
        let ans = suf[0];
        for (let i = 0; i < n-1; i++) {
            ans = Math.min(ans, pre[i]+suf[i+1]);
        }
        ans = Math.min(ans, pre[n-1]);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s, since we scan the string three times.
  • 🧺 Space complexity: O(n), for prefix and suffix arrays.