flip-string-to-monotone-increasing

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

A binary string is monotone increasing if it consists of some number of <code>0</code>&#39;s (possibly none), followed by some number of <code>1</code>&#39;s (also possibly none).

You are given a binary string <code>s</code>. You can flip <code>s[i]</code> changing it from <code>0</code> to <code>1</code> or from <code>1</code> to <code>0</code>.

Return the minimum number of flips to make <code>s</code> monotone increasing.

&nbsp;
Example 1:

<pre>
Input: s = &quot;00110&quot;
Output: 1
Explanation: We flip the last digit to get 00111.
</pre>

Example 2:

<pre>
Input: s = &quot;010110&quot;
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.
</pre>

Example 3:

<pre>
Input: s = &quot;00011000&quot;
Output: 2
Explanation: We flip to get 00000000.
</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>

minFlipsMonoIncr

Flip String to Monotone Increasing

Minimum Cost to Make All Characters Equal

minimum-cost-to-make-all-characters-equal

使所有字符相等的最小成本

String

Dynamic Programming

如果一个二进制字符串，是以一些 <code>0</code>（可能没有 <code>0</code>）后面跟着一些 <code>1</code>（也可能没有 <code>1</code>）的形式组成的，那么该字符串是 单调递增 的。

给你一个二进制字符串 <code>s</code>，你可以将任何 <code>0</code> 翻转为 <code>1</code> 或者将 <code>1</code> 翻转为 <code>0</code> 。

返回使 <code>s</code> 单调递增的最小翻转次数。

&nbsp;

示例 1：

<pre>
输入：s = "00110"
输出：1
解释：翻转最后一位得到 00111.
</pre>

示例 2：

<pre>
输入：s = "010110"
输出：2
解释：翻转得到 011111，或者是 000111。
</pre>

示例 3：

<pre>
输入：s = "00011000"
输出：2
解释：翻转得到 00000000。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length &lt;= 105</code></li>
	<li><code>s[i]</code> 为 <code>'0'</code> 或 <code>'1'</code></li>
</ul>