##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2380.html

# 2380. Time Needed to Rearrange a Binary String

• Difficulty: Medium.
• Related Topics: String, Dynamic Programming, Simulation.
• Similar Questions: Minimum Swaps to Group All 1’s Together, Minimum Swaps to Group All 1’s Together II.

## Problem

You are given a binary string s. In one second, all occurrences of "01" are simultaneously replaced with "10". This process repeats until no occurrences of "01" exist.

Return** the number of seconds needed to complete this process.**

Example 1:

Input: s = "0110101"
Output: 4
Explanation:
After one second, s becomes "1011010".
After another second, s becomes "1101100".
After the third second, s becomes "1110100".
After the fourth second, s becomes "1111000".
No occurrence of "01" exists any longer, and the process needed 4 seconds to complete,
so we return 4.


Example 2:

Input: s = "11100"
Output: 0
Explanation:
No occurrence of "01" exists in s, and the processes needed 0 seconds to complete,
so we return 0.


Constraints:

• 1 <= s.length <= 1000

• s[i] is either '0' or '1'.

Can you solve this problem in O(n) time complexity?

## Solution (Java, C++, Python)

• class Solution {
public int secondsToRemoveOccurrences(String s) {
int lastOne = -1;
int result = 0;
int prevResult = 0;
int curResult = 0;
int countOne = 0;
int countZero = 0;
int diff;
int pTarget;
int pWait;
int cTarget;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '0') {
++countZero;
continue;
}
++countOne;
diff = i - lastOne - 1;
prevResult = curResult;
cTarget = countOne - 1;
pTarget = cTarget - 1;
pWait = prevResult - (lastOne - pTarget);
if (diff > pWait) {
curResult = countZero;
} else {
curResult = countZero == 0 ? 0 : pWait - diff + 1 + countZero;
}
result = curResult;
lastOne = i;
}
return result;
}
}

############

class Solution {
public int secondsToRemoveOccurrences(String s) {
int ans = 0, cnt = 0;
for (char c : s.toCharArray()) {
if (c == '0') {
++cnt;
} else if (cnt > 0) {
ans = Math.max(ans + 1, cnt);
}
}
return ans;
}
}

• class Solution:
def secondsToRemoveOccurrences(self, s: str) -> int:
ans = cnt = 0
for c in s:
if c == '0':
cnt += 1
elif cnt:
ans = max(ans + 1, cnt)
return ans

############

# 2380. Time Needed to Rearrange a Binary String
# https://leetcode.com/problems/time-needed-to-rearrange-a-binary-string

class Solution:
def secondsToRemoveOccurrences(self, s: str) -> int:
n = len(s)
res = 0

while "01" in s:
s = s.replace("01", "10")
res += 1

return res


• class Solution {
public:
int secondsToRemoveOccurrences(string s) {
int ans = 0, cnt = 0;
for (char c : s) {
if (c == '0') {
++cnt;
} else if (cnt) {
ans = max(ans + 1, cnt);
}
}
return ans;
}
};

• func secondsToRemoveOccurrences(s string) int {
ans, cnt := 0, 0
for _, c := range s {
if c == '0' {
cnt++
} else if cnt > 0 {
ans = max(ans+1, cnt)
}
}
return ans
}

func max(a, b int) int {
if a > b {
return a
}
return b
}


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).