Apply Operations to Make Two Strings Equal
You are given two 0-indexed binary strings s1 and s2, both of length n, and a positive integer x.
You can perform any of the following operations on the string s1 any number of times:
- Choose two indices
iandj, and flip boths1[i]ands1[j]. The cost of this operation isx. - Choose an index
isuch thati < n - 1and flip boths1[i]ands1[i + 1]. The cost of this operation is1.
Return the minimum cost needed to make the strings s1 and s2 equal, or return -1 if it is impossible.
Note that flipping a character means changing it from 0 to 1 or vice versa.
Example 1
Input
s1 = "1100011000", s2 = "0101001010", x = 2Output
4Using adjacent flips at indices 3 and 4 plus one arbitrary-pair flip at indices 0 and 8 makes
s1 equal to s2 with total cost 4, which is minimum.Example 2
Input
s1 = "10110", s2 = "00011", x = 4Output
-1It is not possible to make the two strings equal.
Constraints
- n == s1.length == s2.length
- 1 <= n, x <= 500
- s1 and s2 consist only of the characters '0' and '1'.