separate-black-and-white-balls

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

There are <code>n</code> balls on a table, each ball has a color black or white.

You are given a 0-indexed binary string <code>s</code> of length <code>n</code>, where <code>1</code> and <code>0</code> represent black and white balls, respectively.

In each step, you can choose two adjacent balls and swap them.

Return the minimum number of steps to group all the black balls to the right and all the white balls to the left.

&nbsp;
Example 1:

<pre>
Input: s = &quot;101&quot;
Output: 1
Explanation: We can group all the black balls to the right in the following way:
- Swap s[0] and s[1], s = &quot;011&quot;.
Initially, 1s are not grouped together, requiring at least 1 step to group them to the right.</pre>

Example 2:

<pre>
Input: s = &quot;100&quot;
Output: 2
Explanation: We can group all the black balls to the right in the following way:
- Swap s[0] and s[1], s = &quot;010&quot;.
- Swap s[1] and s[2], s = &quot;001&quot;.
It can be proven that the minimum number of steps needed is 2.
</pre>

Example 3:

<pre>
Input: s = &quot;0111&quot;
Output: 0
Explanation: All the black balls are already grouped to the right.
</pre>

&nbsp;
Constraints:

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

minimumSteps

Separate Black and White Balls

Greedy

Two Pointers

String

桌子上有 <code>n</code> 个球，每个球的颜色不是黑色，就是白色。

给你一个长度为 <code>n</code> 、下标从 0 开始的二进制字符串 <code>s</code>，其中 <code>1</code> 和 <code>0</code> 分别代表黑色和白色的球。

在每一步中，你可以选择两个相邻的球并交换它们。

返回「将所有黑色球都移到右侧，所有白色球都移到左侧所需的 最小步数」。

&nbsp;

示例 1：

<pre>
输入：s = "101"
输出：1
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "011"。
最开始，1 没有都在右侧，需要至少 1 步将其移到右侧。</pre>

示例 2：

<pre>
输入：s = "100"
输出：2
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "010"。
- 交换 s[1] 和 s[2]，s = "001"。
可以证明所需的最小步数为 2 。
</pre>

示例 3：

<pre>
输入：s = "0111"
输出：0
解释：所有黑色球都已经在右侧。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n == s.length &lt;= 105</code></li>
	<li><code>s[i]</code> 不是 <code>'0'</code>，就是 <code>'1'</code>。</li>
</ul>