# 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 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 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