2167. Minimum Time to Remove All Cars Containing Illegal Goods #

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:

Remove a train car from the left end (i.e., remove s[0]) which takes 1 unit of time.
Remove a train car from the right end (i.e., remove s[s.length - 1]) which takes 1 unit of time.
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 = "1100101"
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 = "0010"
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'.

Problem Summary #

You are given a 0-indexed binary string s, representing a sequence of train cars. s[i] = ‘0’ means the ith car does not contain illegal goods, while s[i] = ‘1’ means the ith car contains illegal goods.

As the train conductor, you need to remove all cars containing illegal goods. You can perform any of the following three operations any number of times:

Remove one car from the left end of the train (i.e., remove s[0]), taking 1 unit of time.
Remove one car from the right end of the train (i.e., remove s[s.length - 1]), taking 1 unit of time.
Remove one car from any position in the train car sequence, taking 2 units of time.

Return the minimum number of time units needed to remove all cars containing illegal goods. Note that an empty train car sequence is considered to have no cars containing illegal goods.

Solution Ideas #

This problem asks for the minimum number of time units. The minimum time must use the operation that takes 2 units of time as little as possible and use more operations that take 1 unit of time. To remove cars from both ends of the train, you only need to remove the metal connection with the adjacent car. Since the car is at an end of the train, it has only 1 metal connection with other cars, so it only takes 1 unit of time; when the car is in the middle, it has 2 metal connections with the cars on both sides, and removing it requires disconnecting it from both sides. Therefore, it takes 2 units of time.
After disconnecting a middle car, the train will be split into 2 parts. The 2 parts each have 2 heads and 2 tails. For example: 1100111101. If it is disconnected starting from the 5th car, the remaining trains are 11001 (1) and 1101. The remaining 1s are all located on the two sides, and removing them only takes 1 unit of time each. Then the minimum time to remove all illegal goods is 2 * 1 + 1 * 6 = 8.
For the left half, define prefixSum[i] as the minimum time spent removing the first i cars. The state transition equation is:
\[ prefixSum[i] =\left\{\begin{matrix}prefixSum[i-1],s[i]=0\\ min(prefixSum[i-1]+2, i+1), s[i]=1\end{matrix}\right. \]
Similarly, for the right half, define suffixSum[i] as the minimum time spent removing the last i cars. The state transition equation is:
\[ suffixSum[i] =\left\{\begin{matrix} suffixSum[i+1],s[i]=0\\ min(suffixSum[i+1]+2, n-i), s[i]=1\end{matrix}\right. \]
Finally, loop through and enumerate the minimum value of prefixSum[i] + suffixSum[i+1], which is the answer.
This problem can be further simplified based on Solution 1. When s[i] = 1, prefixSum and suffixSum are two calculation methods. We can assume that the disconnected middle part is included in prefixSum. Thus, the two state transition equations above can be merged. See Solution 2 for the simplified code.

Code #

package leetcode

import "runtime/debug"

// Solution 1 DP
func minimumTime(s string) int {
	suffixSum, prefixSum, res := make([]int, len(s)+1), make([]int, len(s)+1), 0
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] == '0' {
			suffixSum[i] = suffixSum[i+1]
		} else {
			suffixSum[i] = min(suffixSum[i+1]+2, len(s)-i)
		}
	}
	res = suffixSum[0]
	if s[0] == '1' {
		prefixSum[0] = 1
	}
	for i := 1; i < len(s); i++ {
		if s[i] == '0' {
			prefixSum[i] = prefixSum[i-1]
		} else {
			prefixSum[i] = min(prefixSum[i-1]+2, i+1)
		}
		res = min(res, prefixSum[i]+suffixSum[i+1])
	}
	return res
}

func init() { debug.SetGCPercent(-1) }

// Solution 2 slightly optimizes time and space complexity
func minimumTime1(s string) int {
	res, count := len(s), 0
	for i := 0; i < len(s); i++ {
		count = min(count+int(s[i]-'0')*2, i+1)
		res = min(res, count+len(s)-i-1)
	}
	return res
}

func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}