Minimum Time to Remove All Cars Containing Illegal Goods Solution
Minimum Time to Remove All Cars Containing Illegal Goods solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Time to Remove All Cars Containing Illegal Goods is a hard coding problem on strings, dynamic programming and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A train is described by a binary string s: s[i] = '0' means car i is clean and s[i] = '1' means it carries illegal goods. You must remove every car that carries illegal goods, using any number of these operations:
- remove the car at the left end of the train — 1 unit of time;
- remove the car at the right end of the train — 1 unit of time;
- remove a car from anywhere in the train — 2 units of time.
Return the minimum time needed to remove all cars containing illegal goods. A train with no cars left contains no illegal goods.
Example 1
Input: s = "0110"
Output: 3
Explanation: Remove three cars from the left (or from the right) — cheaper than pulling out both 1s from the middle for 4.
Example 2
Input: s = "1001"
Output: 2
Explanation: One car from each end.
Example 3
Input: s = "0100010"
Output: 4
Explanation: Two cars from the left and two from the right.
Constraints
1 <= s.length <= 2 * 10^5s[i] is either '0' or '1'
Hints for Minimum Time to Remove All Cars Containing Illegal Goods
Hint 1
An optimal plan removes some prefix from the left, some suffix from the right, and every remaining
1in between individually.Hint 2
Let
left[i]be the cheapest way to clear the prefixs[0..i]using left removals and middle removals: either remove the whole prefix from the left (i + 1), or clears[0..i-1]and pay 2 more ifs[i]is1.Hint 3
Then the answer is the minimum over
iofleft[i] + (n - 1 - i)— clear the prefix, take the rest from the right — together withn(take everything from the right).
How to solve Minimum Time to Remove All Cars Containing Illegal Goods
Some prefix goes out of the left end, some suffix out of the right end, and the illegal cars stuck in between are pulled out at 2 each. Scanning left to right, a one-dimensional DP gives the cheapest way to clear each prefix; pairing it with removing everything after it from the right covers every plan.
Approach
left = 0(empty prefix),best = n(everything from the right).- For
ifrom 0 ton - 1:left = min(left + (s[i] == '1' ? 2 : 0), i + 1)— either keep handling the prefix the same way and pull cariout from the middle if needed, or remove the whole prefix0..ifrom the left. best = min(best, left + (n - 1 - i)).- Return
best.
Why it works
In any plan the cars removed from the left form a prefix and the cars removed from the right form a suffix; every other illegal car must be removed individually. For the split point i (the last car not taken from the right), the cheapest handling of s[0..i] is left[i], because the left-removed prefix inside it can end anywhere and the recurrence considers every such end; the suffix after i costs its length. Minimising over i (plus the all-right plan) therefore covers every plan.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Removing a clean car from an end still costs 1 — that is why long clean stretches favour middle removals.
- Do not forget the plan that takes every car from the right (
n), or the one that uses no end removals at all. - Middle removals cost 2 each — pulling out two adjacent 1s at the edge (cost 2) beats pulling them out of the middle (cost 4).
Reference solution
Python
def minimumTime(s: str) -> int:
n = len(s)
left = 0
best = n
for i, ch in enumerate(s):
left = min(left + (2 if ch == '1' else 0), i + 1)
best = min(best, left + n - 1 - i)
return bestJava
public static int minimumTime(String s) {
int n = s.length(), left = 0, best = n;
for (int i = 0; i < n; i++) {
left = Math.min(left + (s.charAt(i) == '1' ? 2 : 0), i + 1);
best = Math.min(best, left + n - 1 - i);
}
return best;
}C++
int minimumTime(string s) {
int n = s.size(), left = 0, best = n;
for (int i = 0; i < n; i++) {
left = min(left + (s[i] == '1' ? 2 : 0), i + 1);
best = min(best, left + n - 1 - i);
}
return best;
}JavaScript
var minimumTime = function(s) {
var n = s.length, left = 0, best = n;
for (var i = 0; i < n; i++) {
left = Math.min(left + (s[i] === '1' ? 2 : 0), i + 1);
best = Math.min(best, left + n - 1 - i);
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming