Minimum Time to Remove All Cars Containing Illegal Goods

Hard
1520.

Minimum Time to Remove All Cars Containing Illegal Goods

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.

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^5
  • s[i] is either '0' or '1'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minimumTime = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Minimum Time to Remove All Cars Containing Illegal Goods

  1. Hint 1

    An optimal plan removes some prefix from the left, some suffix from the right, and every remaining 1 in between individually.

  2. Hint 2

    Let left[i] be the cheapest way to clear the prefix s[0..i] using left removals and middle removals: either remove the whole prefix from the left (i + 1), or clear s[0..i-1] and pay 2 more if s[i] is 1.

  3. Hint 3

    Then the answer is the minimum over i of left[i] + (n - 1 - i) — clear the prefix, take the rest from the right — together with n (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

  1. left = 0 (empty prefix), best = n (everything from the right).
  2. For i from 0 to n - 1: left = min(left + (s[i] == '1' ? 2 : 0), i + 1) — either keep handling the prefix the same way and pull car i out from the middle if needed, or remove the whole prefix 0..i from the left.
  3. best = min(best, left + (n - 1 - i)).
  4. 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 best

Java

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