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>

Biweekly Contest 186

biweekly-contest-186

minOperations

Staff

Minimum Operations to Transform Binary String

String

Dynamic Programming

Greedy

Accepted

Wrong Answer

Memory Limit Exceeded

Output Limit Exceeded

Time Limit Exceeded

Runtime Error

Internal Error

Compile Error

Timeout

Restrictions Failed

cangjie

react

vanillajs

You are given two binary strings s1 and s2 of the same length n.

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

 * Choose an index i such that s1[i] == '0', and change it to '1'.
 * Choose an index i such that 0 <= i < n - 1, and both s1[i] and s1[i + 1] are '1'. Change both characters to '0'.

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

 

Example 1:

Input: s1 = "11", s2 = "00"

Output: 1

Explanation:

Change indices 0 and 1 from '1' to '0' in one operation, so "11" becomes "00". Thus, the answer is 1.

Example 2:

Input: s1 = "01", s2 = "10"

Output: 3

Explanation:

 * Change index 0 from '0' to '1', so "01" becomes "11".
 * Change indices 0 and 1 from '1' to '0', so "11" becomes "00".
 * Change index 0 from '0' to '1', so "00" becomes "10".
 * Thus, the answer is 3.

Example 3:

Input: s1 = "1", s2 = "0"

Output: -1

Explanation:

The first operation cannot change '1' to '0', and the second operation requires two adjacent characters. Therefore, it is impossible.

 

Constraints:

 * 1 <= n == s1.length == s2.length <= 105
 * s1 and s2 consist only of '0' and '1'.