2167. Minimum Time to Remove All Cars Containing Illegal Goods LeetCode Solution
In this guide, you will get 2167. Minimum Time to Remove All Cars Containing Illegal Goods LeetCode Solution with the best time and space complexity. The solution to Minimum Time to Remove All Cars Containing Illegal Goods problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Time to Remove All Cars Containing Illegal Goods
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.
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.
1 <= s.length <= 2 * 105
s[i] is either '0' or '1'.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2167. Minimum Time to Remove All Cars Containing Illegal Goods LeetCode Solution in C++
class Solution {
public:
int minimumTime(string s) {
const int n = s.length();
// left[i] := the minimum time to remove the illegal cars of s[0..i]
vector<int> left(n);
left[0] = s[0] - '0';
// dp[i] := the minimum time to remove the illegal cars of s[0..i] optimally
// + the time to remove the illegal cars of s[i + 1..n) consecutively
// Note that the way to remove the illegal cars in the right part
// doesn't need to be optimal since:
// `left | illegal cars | n - 1 - k` will be covered in
// `left' | n - 1 - i` later.
vector<int> dp(n, n);
dp[0] = left[0] + n - 1;
for (int i = 1; i < n; ++i) {
left[i] = min(left[i - 1] + (s[i] - '0') * 2, i + 1);
dp[i] = min(dp[i], left[i] + n - 1 - i);
}
return ranges::min(dp);
}
}; /* code provided by PROGIEZ */
2167. Minimum Time to Remove All Cars Containing Illegal Goods LeetCode Solution in Java
class Solution {
public int minimumTime(String s) {
final int n = s.length();
// left[i] := the minimum time to remove the illegal cars of s[0..i]
int[] left = new int[n];
left[0] = s.charAt(0) - '0';
// dp[i] := the minimum time to remove the illegal cars of s[0..i] optimally
// + the time to remove the illegal cars of s[i + 1..n) consecutively
// Note that the way to remove the illegal cars in the right part
// doesn't need to be optimal since:
// `left | illegal cars | n - 1 - k` will be covered in
// `left' | n - 1 - i` later.
int[] dp = new int[n];
Arrays.fill(dp, n);
dp[0] = left[0] + n - 1;
for (int i = 1; i < n; ++i) {
left[i] = Math.min(left[i - 1] + (s.charAt(i) - '0') * 2, i + 1);
dp[i] = Math.min(dp[i], left[i] + n - 1 - i);
}
return Arrays.stream(dp).min().getAsInt();
}
} // code provided by PROGIEZ
2167. Minimum Time to Remove All Cars Containing Illegal Goods LeetCode Solution in Python
class Solution:
def minimumTime(self, s: str) -> int:
n = len(s)
# left[i] := the minimum time to remove the illegal cars of s[0..i]
left = [0] * n
left[0] = int(s[0])
# dp[i] := the minimum time to remove the illegal cars of s[0..i] optimally
# + the time to remove the illegal cars of s[i + 1..n) consecutively
# Note that the way to remove the illegal cars in the right part
# doesn't need to be optimal since:
# `left | illegal cars | n - 1 - k` will be covered in
# `left' | n - 1 - i` later.
dp = [n] * n
dp[0] = left[0] + n - 1
for i in range(1, n):
left[i] = min(left[i - 1] + int(s[i]) * 2, i + 1)
dp[i] = min(dp[i], left[i] + n - 1 - i)
return min(dp) # code by PROGIEZ
