minimum-operations-to-equalize-binary-string

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>, and an integer <code>k</code>.

In one operation, you must choose exactly <code>k</code> different indices and flip each <code>&#39;0&#39;</code> to <code>&#39;1&#39;</code> and each <code>&#39;1&#39;</code> to <code>&#39;0&#39;</code>.

Return the minimum number of operations required to make all characters in the string equal to <code>&#39;1&#39;</code>. If it is not possible, return -1.

&nbsp;
Example 1:

<div class="example-block">
Input: s = &quot;110&quot;, k = 1

Output: 1

Explanation:

<ul>
	<li>There is one <code>&#39;0&#39;</code> in <code>s</code>.</li>
	<li>Since <code>k = 1</code>, we can flip it directly in one operation.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: s = &quot;0101&quot;, k = 3

Output: 2

Explanation:

One optimal set of operations choosing <code>k = 3</code> indices in each operation is:

<ul>
	<li>Operation 1: Flip indices <code>[0, 1, 3]</code>. <code>s</code> changes from <code>&quot;0101&quot;</code> to <code>&quot;1000&quot;</code>.</li>
	<li>Operation 2: Flip indices <code>[1, 2, 3]</code>. <code>s</code> changes from <code>&quot;1000&quot;</code> to <code>&quot;1111&quot;</code>.</li>
</ul>

Thus, the minimum number of operations is 2.
</div>

Example 3:

<div class="example-block">
Input: s = &quot;101&quot;, k = 2

Output: -1

Explanation:

Since <code>k = 2</code> and <code>s</code> has only one <code>&#39;0&#39;</code>, it is impossible to flip exactly <code>k</code> indices to make all <code>&#39;1&#39;</code>. Hence, the answer is -1.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length &lt;= 10​​​​​​​5</code></li>
	<li><code>s[i]</code> is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
	<li><code>1 &lt;= k &lt;= s.length</code></li>
</ul>