#2896
Apply Operations to Make Two Strings Equal
expert · 1150 · lc medium +32 · verified · 27.6% accepted · 394 likes · top 6%
Description
Two 0-indexed binary strings s1 and s2 of equal length n and a positive integer x are given. You may perform any number of operations on s1:
- Choose indices i and j and flip both s1[i] and s1[j]. Cost: x.
- Choose index i < n - 1 and flip both s1[i] and s1[i + 1]. Cost: 1.
Return the minimum total cost to transform s1 into s2, or -1 if it is impossible.
Flipping changes a 0 to 1 or a 1 to 0.
Example 1:
Input: s1 = "1100011000", s2 = "0101001010", x = 2
Output: 4
Explanation: We can do the following operations:
- Choose i = 3 and apply the second operation. The resulting string is s1 = "1101111000".
- Choose i = 4 and apply the second operation. The resulting string is s1 = "1101001000".
- Choose i = 0 and j = 8 and apply the first operation. The resulting string is s1 = "0101001010" = s2.
The total cost is 1 + 1 + 2 = 4. It can be shown that it is the minimum cost possible.
Example 2:
Input: s1 = "10110", s2 = "00011", x = 4
Output: -1
Explanation: It is not possible to make the two strings equal.
Code
1
2
3