minimum-number-of-flips-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

You are given a binary string <code>s</code>. You are allowed to perform two types of operations on the string in any sequence:

<ul>
	<li>Type-1: Remove the character at the start of the string <code>s</code> and append it to the end of the string.</li>
	<li>Type-2: Pick any character in <code>s</code> and flip its value, i.e., if its value is <code>&#39;0&#39;</code> it becomes <code>&#39;1&#39;</code> and vice-versa.</li>
</ul>

Return the minimum number of type-2 operations you need to perform such that <code>s</code> becomes alternating.

The string is called alternating if no two adjacent characters are equal.

<ul>
	<li>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.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input: s = &quot;111000&quot;
Output: 2
Explanation: Use the first operation two times to make s = &quot;100011&quot;.
Then, use the second operation on the third and sixth elements to make s = &quot;101010&quot;.
</pre>

Example 2:

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

Example 3:

<pre>
Input: s = &quot;1110&quot;
Output: 1
Explanation: Use the second operation on the second element to make s = &quot;1010&quot;.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= 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>

minFlips

Minimum Number of Flips to Make the Binary String Alternating

Minimum Operations to Make the Array Alternating

minimum-operations-to-make-the-array-alternating

使数组变成交替数组的最少操作数

Greedy

String

Dynamic Programming

Sliding Window

给你一个二进制字符串 <code>s</code> 。你可以按任意顺序执行以下两种操作任意次：

<ul>
	<li>类型 1 ：删除 字符串 <code>s</code> 的第一个字符并将它 添加 到字符串结尾。</li>
	<li>类型 2 ：选择 字符串 <code>s</code> 中任意一个字符并将该字符 反转 ，也就是如果值为 <code>'0'</code> ，则反转得到 <code>'1'</code> ，反之亦然。</li>
</ul>

请你返回使 <code>s</code> 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。

我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。

<ul>
	<li>比方说，字符串 <code>"010"</code> 和 <code>"1010"</code> 都是交替的，但是字符串 <code>"0100"</code> 不是。</li>
</ul>

 

示例 1：

<pre>输入：s = "111000"
输出：2
解释：执行第一种操作两次，得到 s = "100011" 。
然后对第三个和第六个字符执行第二种操作，得到 s = "101010" 。
</pre>

示例 2：

<pre>输入：s = "010"
输出：0
解释：字符串已经是交替的。
</pre>

示例 3：

<pre>输入：s = "1110"
输出：1
解释：对第二个字符执行第二种操作，得到 s = "1010" 。
</pre>

 

提示：

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