time-needed-to-rearrange-a-binary-string

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given a binary string <code>s</code>. In one second, all occurrences of <code>&quot;01&quot;</code> are simultaneously replaced with <code>&quot;10&quot;</code>. This process repeats until no occurrences of <code>&quot;01&quot;</code> exist.

Return the number of seconds needed to complete this process.

&nbsp;
Example 1:

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

Example 2:

<pre>
Input: s = &quot;11100&quot;
Output: 0
Explanation:
No occurrence of &quot;01&quot; exists in s, and the processes needed 0 seconds to complete,
so we return 0.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s[i]</code> is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

&nbsp;
Follow up:

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

第 85 场双周赛

biweekly-contest-85

secondsToRemoveOccurrences

高级工程师

Time Needed to Rearrange a Binary String

Minimum Swaps to Group All 1's Together

minimum-swaps-to-group-all-1s-together

最少交换次数来组合所有的 1

Minimum Swaps to Group All 1's Together II

minimum-swaps-to-group-all-1s-together-ii

最少交换次数来组合所有的 1 II

String

Dynamic Programming

Simulation

给你一个二进制字符串&nbsp;<code>s</code>&nbsp;。在一秒之中，所有&nbsp;子字符串&nbsp;<code>"01"</code> 同时&nbsp;被替换成&nbsp;<code>"10"</code>&nbsp;。这个过程持续进行到没有&nbsp;<code>"01"</code>&nbsp;存在。

请你返回完成这个过程所需要的秒数。

&nbsp;

示例 1：

<pre>
输入：s = "0110101"
输出：4
解释：
一秒后，s 变成 "1011010" 。
再过 1 秒后，s 变成 "1101100" 。
第三秒过后，s 变成 "1110100" 。
第四秒后，s 变成 "1111000" 。
此时没有 "01" 存在，整个过程花费 4 秒。
所以我们返回 4 。
</pre>

示例 2：

<pre>
输入：s = "11100"
输出：0
解释：
s 中没有 "01" 存在，整个过程花费 0 秒。
所以我们返回 0 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s[i]</code>&nbsp;要么是&nbsp;<code>'0'</code>&nbsp;，要么是&nbsp;<code>'1'</code> 。</li>
</ul>

&nbsp;

进阶：

你能以 O(n) 的时间复杂度解决这个问题吗？