---
# System prepended metadata

title: 2380. Time Needed to Rearrange a Binary String
tags: [Leetcode, Dynamic Programming, Medium]

---

# 2380. Time Needed to Rearrange a Binary String
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/time-needed-to-rearrange-a-binary-string/description/
## 思路
### Dynamic Programming
0011->0101->1010->1100
每一个1 一秒最多往前动一步
所以一个条件是前面有多少个0就需要多少时间
如果碰到1前面是连续的一个或多个1 后面的就要等前面的 ```seconds[i] = seconds[i-1]+1```
如果碰到的1前面是0那么就需要这个1跟之前的1相比就要多跨过一个0 所以还是```seconds[i] = seconds[i-1]+1```
### Brute Force $O(N^2)$ $O(1)$
注意语法```s=s.replace()```
## Code
### Dynamic Programming
```java=
class Solution {
    public int secondsToRemoveOccurrences(String s) {
        int zeros=0, second=0;
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i)=='0') zeros++;
            else if(s.charAt(i)=='1' && zeros>0) second = Math.max(second+1, zeros);
        }
        return second;
    }
}
```
### Brute Force
```java=
class Solution {
    public int secondsToRemoveOccurrences(String s) {
        int second = 0;
        while(s.indexOf("01")>=0){
            s = s.replace("01", "10");
            second++;
        }
        return second;
    }
}
```