Tap here to switch tabs
Problem
Submissions

Problem: Minimum Operations to Transform Binary String

Minimum Operations to Transform Binary String asks for the fewest operations to turn one binary string into another: flip a zero to one or turn adjacent ones into zeros, or return -1 if impossible.

Statement

You are given two binary strings s1 and s2, both of length n.

In a single operation, you can apply one of the following modifications to s1:

  1. Choose an index i where s1[i] is equal to $'0'$, and change s1[i] to $'1'$.

  2. Choose two adjacent indices i and i + 1 where both s1[i] and s1[i + 1] are equal to $'1'$, and change both characters to $'0'$.

Return the minimum number of operations needed to transform s1 into s2. If it is impossible to transform s1 into s2, return −1-1.

Constraints:

  • 1≤‘n‘=‘s1.length‘=‘s2.length‘≤1051 \leq `n` = `s1.length` = `s2.length` \leq 10^5

  • s1 and s2 consist only of $'0'$ and $'1'$.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimum Operations to Transform Binary String

Minimum Operations to Transform Binary String asks for the fewest operations to turn one binary string into another: flip a zero to one or turn adjacent ones into zeros, or return -1 if impossible.

Statement

You are given two binary strings s1 and s2, both of length n.

In a single operation, you can apply one of the following modifications to s1:

  1. Choose an index i where s1[i] is equal to $'0'$, and change s1[i] to $'1'$.

  2. Choose two adjacent indices i and i + 1 where both s1[i] and s1[i + 1] are equal to $'1'$, and change both characters to $'0'$.

Return the minimum number of operations needed to transform s1 into s2. If it is impossible to transform s1 into s2, return −1-1.

Constraints:

  • 1≤‘n‘=‘s1.length‘=‘s2.length‘≤1051 \leq `n` = `s1.length` = `s2.length` \leq 10^5

  • s1 and s2 consist only of $'0'$ and $'1'$.