Skip to content

Latest commit

 

History

History
148 lines (117 loc) · 6.2 KB

README.md

File metadata and controls

148 lines (117 loc) · 6.2 KB
Raw

2167. Minimum Time to Remove All Cars Containing Illegal Goods (Hard)

You are given a 0-indexed binary string s which represents a sequence of train cars. s[i] = '0' denotes that the ith car does not contain illegal goods and s[i] = '1' denotes that the ith car does contain illegal goods.

As the train conductor, you would like to get rid of all the cars containing illegal goods. You can do any of the following three operations any number of times:

  1. Remove a train car from the left end (i.e., remove s[0]) which takes 1 unit of time.
  2. Remove a train car from the right end (i.e., remove s[s.length - 1]) which takes 1 unit of time.
  3. Remove a train car from anywhere in the sequence which takes 2 units of time.

Return the minimum time to remove all the cars containing illegal goods.

Note that an empty sequence of cars is considered to have no cars containing illegal goods.

 

Example 1:

Input: s = "1100101"
Output: 5
Explanation: 
One way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the left end 2 times. Time taken is 2 * 1 = 2.
- remove a car from the right end. Time taken is 1.
- remove the car containing illegal goods found in the middle. Time taken is 2.
This obtains a total time of 2 + 1 + 2 = 5. 

An alternative way is to
- remove a car from the left end 2 times. Time taken is 2 * 1 = 2.
- remove a car from the right end 3 times. Time taken is 3 * 1 = 3.
This also obtains a total time of 2 + 3 = 5.

5 is the minimum time taken to remove all the cars containing illegal goods. 
There are no other ways to remove them with less time.

Example 2:

Input: s = "0010"
Output: 2
Explanation:
One way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the left end 3 times. Time taken is 3 * 1 = 3.
This obtains a total time of 3.

Another way to remove all the cars containing illegal goods from the sequence is to
- remove the car containing illegal goods found in the middle. Time taken is 2.
This obtains a total time of 2.

Another way to remove all the cars containing illegal goods from the sequence is to 
- remove a car from the right end 2 times. Time taken is 2 * 1 = 2. 
This obtains a total time of 2.

2 is the minimum time taken to remove all the cars containing illegal goods. 
There are no other ways to remove them with less time.

 

Constraints:

  • 1 <= s.length <= 2 * 105
  • s[i] is either '0' or '1'.

Similar Questions:

Solution 1.

The string needs to be split into 3 segments:

  • We delete all the numbers in the left part
  • We only delete the ones in the middle part
  • We delete all the numbers in the right part

Ignoring the ones at the edges which must be removed using 1 unit of time, the rest of elements will be in the following form

| left   |        middle      | right |
0..0  1..1  0...0 1..1 0...0  1..1 0..0

Assume there are x ones in the middle, and one ones and zero zeroes in the right. The left part is symmetric to the right part so we ignore it for now.

The total cost is 2x + one + zero = 2(x+one) + zero - one. x + one is the total number of ones in s which is a constant. So our goal is to minimize zero - one in the left part and right part.

We can traverse from left to right, and calculate the zero - one value of the left part. For the min zero - one in the right part, we can use a mono-stack to precompute it.

// OJ: https://leetcode.com/problems/minimum-time-to-remove-all-cars-containing-illegal-goods/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int minimumTime(string s) {
        int cnt = 0, N = s.size(), ans = INT_MAX;
        for (char c : s) cnt += c == '1';
        vector<int> right(N + 1);
        stack<int> st{{N}};
        for (int i = N - 1; i >= 0; --i) {
            right[i] = right[i + 1] + (s[i] == '0' ? 1 : -1);
            if (right[i] < right[st.top()]) st.push(i);
        }
        for (int i = 0, diff = 0; i < N; ++i) {
            ans = min(ans, 2 * cnt + diff + right[st.top()]);
            diff += s[i] == '0' ? 1 : -1;
            if (st.top() == i) st.pop();
        }
        return ans;
    }
};

Solution 2. DP

right[i] is the min cost to remove 1s in s[i:] using operation 2 and 3.

  • If s[i] == '0', right[i] = right[i + 1].
  • If s[i] == '1':
    • If we use operation 3, right[i] = right[i + 1] + 2.
    • If we use operation 2, right[i] = N - i.
    • So, right[i] = min( right[i + 1] + 2, N - i )

Now scan from left to right. For each s[i], we remove s[0..(i-1)] using operation 1 with cost i. Since right[i] is the min cost to remove 1s in s[i:] using operation 2 and 3. The optimal total cost for this index i is i + right[i]. The answer is the global min i + right[i].

// OJ: https://leetcode.com/problems/minimum-time-to-remove-all-cars-containing-illegal-goods/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int minimumTime(string s) {
        int cnt = 0, N = s.size(), ans = INT_MAX;
        vector<int> right(N + 1);
        for (int i = N - 1; i >= 0; --i) {
            if (s[i] == '0') right[i] = right[i + 1];
            else right[i] = min(right[i + 1] + 2, N - i);
        }
        for (int i = 0; i < N; ++i) {
            ans = min(ans, i + right[i]);
        }
        return ans;
    }
};