minimum-flips-to-make-binary-string-coherent

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given a binary string <code>s</code>.

A string is considered coherent if it does not contain <code>&quot;011&quot;</code> or <code>&quot;110&quot;</code> as subsequences.

In one operation, you can flip any character in <code>s</code> (<code>&#39;0&#39;</code> to <code>&#39;1&#39;</code> or <code>&#39;1&#39;</code> to <code>&#39;0&#39;</code>).

Return an integer denoting the minimum number of operations required to make <code>s</code> coherent.

&nbsp;
Example 1:

<div class="example-block">
Input: s = &quot;1010&quot;

Output: 1

Explanation:

Flip <code>s[0]</code> to get <code>&quot;0010&quot;</code>, which contains no <code>&quot;011&quot;</code> or <code>&quot;110&quot;</code> subsequences.
</div>

Example 2:

<div class="example-block">
Input: s = &quot;0110&quot;

Output: 1

Explanation:

Flip <code>s[1]</code> to get <code>&quot;0010&quot;</code>, removing all forbidden subsequences <code>&quot;011&quot;</code> and <code>&quot;110&quot;</code>.
</div>

Example 3:

<div class="example-block">
Input: s = &quot;1000&quot;

Output: 0

Explanation:

The string already has no <code>&quot;011&quot;</code> or <code>&quot;110&quot;</code> subsequences, so no flips are needed.
</div>

&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>