minimum-number-of-swaps-to-make-the-binary-string-alternating

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given a binary string <code>s</code>, return the minimum number of character swaps to make it alternating, or <code>-1</code> if it is impossible.

The string is called alternating if no two adjacent characters are equal. For example, the strings <code>&quot;010&quot;</code> and <code>&quot;1010&quot;</code> are alternating, while the string <code>&quot;0100&quot;</code> is not.

Any two characters may be swapped, even if they are&nbsp;not adjacent.

&nbsp;
Example 1:

<pre>
Input: s = &quot;111000&quot;
Output: 1
Explanation: Swap positions 1 and 4: &quot;111000&quot; -&gt; &quot;101010&quot;
The string is now alternating.
</pre>

Example 2:

<pre>
Input: s = &quot;010&quot;
Output: 0
Explanation: The string is already alternating, no swaps are needed.
</pre>

Example 3:

<pre>
Input: s = &quot;1110&quot;
Output: -1
</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>

minSwaps

Minimum Number of Swaps to Make the Binary String Alternating

Greedy

String

给你一个二进制字符串 <code>s</code> ，现需要将其转化为一个 交替字符串 。请你计算并返回转化所需的 最小 字符交换次数，如果无法完成转化，返回 <code>-1</code> 。

交替字符串 是指：相邻字符之间不存在相等情况的字符串。例如，字符串 <code>"010"</code> 和 <code>"1010"</code> 属于交替字符串，但 <code>"0100"</code> 不是。

任意两个字符都可以进行交换，不必相邻 。

 

示例 1：

<pre>
输入：s = "111000"
输出：1
解释：交换位置 1 和 4："111000" -> "101010" ，字符串变为交替字符串。
</pre>

示例 2：

<pre>
输入：s = "010"
输出：0
解释：字符串已经是交替字符串了，不需要交换。
</pre>

示例 3：

<pre>
输入：s = "1110"
输出：-1
</pre>

 

提示：

<ul>
	<li><code>1 <= s.length <= 1000</code></li>
	<li><code>s[i]</code> 的值为 <code>'0'</code> 或 <code>'1'</code></li>
</ul>