minimum-operations-to-transform-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 two binary strings <code>s1</code> and <code>s2</code> of the same length <code>n</code>.

You can perform the following operations on <code>s1</code> any number of times, in any order:

<ul>
	<li>Choose an index <code>i</code> such that <code>s1[i] == &#39;0&#39;</code>, and change it to <code>&#39;1&#39;</code>.</li>
	<li>Choose an index <code>i</code> such that <code>0 &lt;= i &lt; n - 1</code>, and both <code>s1[i]</code> and <code>s1[i + 1]</code> are <code>&#39;1&#39;</code>. Change both characters to <code>&#39;0&#39;</code>.</li>
</ul>

Return the minimum number of operations required to make <code>s1</code> equal to <code>s2</code>. If it is impossible, return -1.

&nbsp;
Example 1:

<div class="example-block">
Input: s1 = &quot;11&quot;, s2 = &quot;00&quot;

Output: 1

Explanation:

Change indices 0 and 1 from <code>&#39;1&#39;</code> to <code>&#39;0&#39;</code> in one operation, so <code>&quot;11&quot;</code> becomes <code>&quot;00&quot;</code>. Thus, the answer is 1.
</div>

Example 2:

<div class="example-block">
Input: s1 = &quot;01&quot;, s2 = &quot;10&quot;

Output: 3

Explanation:

<ul>
	<li>Change index 0 from <code>&#39;0&#39;</code> to <code>&#39;1&#39;</code>, so <code>&quot;01&quot;</code> becomes <code>&quot;11&quot;</code>.</li>
	<li>Change indices 0 and 1 from <code>&#39;1&#39;</code> to <code>&#39;0&#39;</code>, so <code>&quot;11&quot;</code> becomes <code>&quot;00&quot;</code>.</li>
	<li>Change index 0 from <code>&#39;0&#39;</code> to <code>&#39;1&#39;</code>, so <code>&quot;00&quot;</code> becomes <code>&quot;10&quot;</code>.</li>
	<li>Thus, the answer is 3.</li>
</ul>
</div>

Example 3:

<div class="example-block">
Input: s1 = &quot;1&quot;, s2 = &quot;0&quot;

Output: -1

Explanation:

The first operation cannot change <code>&#39;1&#39;</code> to <code>&#39;0&#39;</code>, and the second operation requires two adjacent characters. Therefore, it is impossible.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n == s1.length == s2.length &lt;= 105</code></li>
	<li><code>s1</code> and <code>s2</code> consist only of <code>&#39;0&#39;</code> and <code>&#39;1&#39;</code>.</li>
</ul>