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
class Solution {
 public:
  int minimumTime(string s) {
    const int n = s.length();
    // left[i] := min time to remove illegal cars of s[0..i]
    vector<int> left(n);
    left[0] = s[0] - '0';
    // dp[i] := min time to remove illegal cars of s[0..i] in optimal fashion +
    //              time to remove illegal cars of s[i + 1..n - 1] consecutively
    // Note the way to remove 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 *min_element(begin(dp), end(dp));
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int minimumTime(String s) {
    final int n = s.length();
    // left[i] := min time to remove illegal cars of s[0..i]
    int[] left = new int[n];
    left[0] = s.charAt(0) - '0';
    // dp[i] := min time to remove illegal cars of s[0..i] in optimal fashion +
    //              time to remove illegal cars of s[i + 1..n - 1] consecutively
    // Note the way to remove 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
class Solution:
  def minimumTime(self, s: str) -> int:
    n = len(s)
    # left[i] := min time to remove illegal cars of s[0..i]
    left = [0] * n
    left[0] = ord(s[0]) - ord('0')
    # dp[i] := min time to remove illegal cars of s[0..i] in optimal fashion +
    #              time to remove illegal cars of s[i + 1..n - 1] consecutively
    # Note the way to remove 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] + (ord(s[i]) - ord('0')) * 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;  // Min time to remove 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; // Min time to remove 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  # Min time to remove illegal cars so far

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

    return ans