Problem


Key Idea

Think of two pointers.

  • left: minimum time to clear ‘1’s from s[0] to s[i]
  • right: minimum time to clear ‘1’s from s[i+1] to s[n-1]

While iteratating from left to right,

update left value with minimum of those two:

  • left+2 (cost of removing s[i] without removing prefix)
  • i+1 (cost of removing prefix all the way to s[i])

update right value with:

  • n - 1 - i (cost of removing all cars from the right)

Update ans during the iteration.

\[ans = \min_{\rm i} (left_i + right_i)\]


  • Time: \(O(n)\)
  • Space: \(O(1)\)

Implementation

/**
 * written: 2022. 02. 11. Fri. 16:57:01 [UTC+9]
 * jooncco의 mac에서.
 **/

class Solution {
public:
    int minimumTime(string s) {
        int n= s.length(), l= 0, ans= n;
        for (int i=0; i < n; ++i) {
            l= min(l + 2*(s[i] == '1'), i+1);
            ans= min(ans, l + n-1-i);
        }
        return ans;
    }
};

Leave a comment