Skip to content

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

Approach 1: $O(n)$ space

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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)

Approach 2: $O(1)$ space

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int minimumTime(string s) {
    const int n = s.length();
    int ans = n;
    int left = 0;  // the minimum time to remove the illegal cars so far

    for (int i = 0; i < n; ++i) {
      left = min(left + (s[i] - '0') * 2, i + 1);
      ans = min(ans, left + n - 1 - i);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public int minimumTime(String s) {
    final int n = s.length();
    int ans = n;
    int left = 0; // the minimum time to remove the illegal cars so far

    for (int i = 0; i < n; ++i) {
      left = Math.min(left + (s.charAt(i) - '0') * 2, i + 1);
      ans = Math.min(ans, left + n - 1 - i);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def minimumTime(self, s: str) -> int:
    n = len(s)
    ans = n
    left = 0  # the minimum time to remove the illegal cars so far

    for i, c in enumerate(s):
      left = min(left + int(c) * 2, i + 1)
      ans = min(ans, left + n - 1 - i)

    return ans