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