Algorithms
Medium
2896
3033
Apply Operations to Make Two Strings Equal
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 i and j, and flip both s1[i] and s1[j]. The cost of this operation is x.
 * Choose an index i such that i < n - 1 and flip both s1[i] and s1[i + 1]. The cost of this operation is 1.

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 = 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.


Constraints:

 * n == s1.length == s2.length
 * 1 <= n, x <= 500
 * s1 and s2 consist only of the characters '0' and '1'.
"""
class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        
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 i and j, and flip both s1[i] and s1[j]. The cost of this operation is x.
 * Choose an index i such that i < n - 1 and flip both s1[i] and s1[i + 1]. The cost of this operation is 1.

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 = 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.


Constraints:

 * n == s1.length == s2.length
 * 1 <= n, x <= 500
 * s1 and s2 consist only of the characters '0' and '1'.


Please complete the code below to solve above prblem:
```python
class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        
```

my_solution = Solution()

test_input = { "s1": "1100011000", "s2": "0101001010", "x": 2 }
assert my_solution.minOperations(**test_input) == 4

test_input = { "s1": "10110", "s2": "00011", "x": 4 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "101101", "s2": "000000", "x": 6 }
assert my_solution.minOperations(**test_input) == 4

test_input = { "s1": "0", "s2": "1", "x": 2 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "1011100100111000", "s2": "1001010001011100", "x": 19 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "00101101100010", "s2": "00001010001111", "x": 30 }
assert my_solution.minOperations(**test_input) == 8

test_input = { "s1": "1011000", "s2": "0001101", "x": 30 }
assert my_solution.minOperations(**test_input) == 4

test_input = { "s1": "1111110101010110", "s2": "1000100111100101", "x": 19 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "1011100000100100101", "s2": "1110001001110000011", "x": 14 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "0", "s2": "1", "x": 17 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "0", "s2": "1", "x": 3 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "0001110010", "s2": "0110100111", "x": 29 }
assert my_solution.minOperations(**test_input) == 5

test_input = { "s1": "01111101010100110100", "s2": "10010011011001011000", "x": 21 }
assert my_solution.minOperations(**test_input) == 7

test_input = { "s1": "00000101", "s2": "01001010", "x": 10 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "01", "s2": "00", "x": 30 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "11111", "s2": "01011", "x": 4 }
assert my_solution.minOperations(**test_input) == 2

test_input = { "s1": "001010101011001", "s2": "110111000101110", "x": 14 }
assert my_solution.minOperations(**test_input) == 7

test_input = { "s1": "010011101", "s2": "101111000", "x": 17 }
assert my_solution.minOperations(**test_input) == 4

test_input = { "s1": "11110111", "s2": "10011111", "x": 16 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "0011", "s2": "1100", "x": 14 }
assert my_solution.minOperations(**test_input) == 2

test_input = { "s1": "000011", "s2": "010101", "x": 27 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "01111010", "s2": "10110011", "x": 21 }
assert my_solution.minOperations(**test_input) == 4

test_input = { "s1": "10010111001", "s2": "11101011110", "x": 1 }
assert my_solution.minOperations(**test_input) == 4

test_input = { "s1": "10001", "s2": "11000", "x": 11 }
assert my_solution.minOperations(**test_input) == 3

test_input = { "s1": "11001011111", "s2": "01111000110", "x": 2 }
assert my_solution.minOperations(**test_input) == 4

test_input = { "s1": "111010100001011", "s2": "100000101100111", "x": 29 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "010000110111000111", "s2": "100011100010010111", "x": 15 }
assert my_solution.minOperations(**test_input) == 6

test_input = { "s1": "010010111", "s2": "011100010", "x": 21 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "01011111", "s2": "11110101", "x": 7 }
assert my_solution.minOperations(**test_input) == 4

test_input = { "s1": "00001011110000", "s2": "01011110001001", "x": 12 }
assert my_solution.minOperations(**test_input) == 8

test_input = { "s1": "1100110100001001", "s2": "0100111010111001", "x": 18 }
assert my_solution.minOperations(**test_input) == 8

test_input = { "s1": "00101101", "s2": "10010101", "x": 6 }
assert my_solution.minOperations(**test_input) == 3

test_input = { "s1": "110010", "s2": "011011", "x": 21 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "00101", "s2": "11000", "x": 25 }
assert my_solution.minOperations(**test_input) == 3

test_input = { "s1": "110", "s2": "100", "x": 27 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "1101", "s2": "0000", "x": 9 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "11", "s2": "01", "x": 7 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "100000000", "s2": "001011111", "x": 26 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "0111001011", "s2": "0010011111", "x": 21 }
assert my_solution.minOperations(**test_input) == 4

test_input = { "s1": "10", "s2": "00", "x": 19 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "110111", "s2": "101101", "x": 3 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "1010111", "s2": "0110011", "x": 25 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "001", "s2": "101", "x": 19 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "111100000100111", "s2": "110100010110001", "x": 7 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "111", "s2": "110", "x": 4 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "10000010010", "s2": "11100000010", "x": 22 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "00100110", "s2": "10101111", "x": 16 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "0110010001101011010", "s2": "1011110101000001100", "x": 3 }
assert my_solution.minOperations(**test_input) == 8

test_input = { "s1": "0001100000001", "s2": "0011000011101", "x": 28 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "0000110011", "s2": "0000000011", "x": 3 }
assert my_solution.minOperations(**test_input) == 1

test_input = { "s1": "11101100", "s2": "11111011", "x": 10 }
assert my_solution.minOperations(**test_input) == 3

test_input = { "s1": "011101110001001010", "s2": "111000011001101010", "x": 30 }
assert my_solution.minOperations(**test_input) == 8

test_input = { "s1": "1111111100", "s2": "1010001010", "x": 5 }
assert my_solution.minOperations(**test_input) == 4

test_input = { "s1": "111011", "s2": "111010", "x": 19 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "00010", "s2": "00010", "x": 9 }
assert my_solution.minOperations(**test_input) == 0

test_input = { "s1": "11100000", "s2": "11110010", "x": 13 }
assert my_solution.minOperations(**test_input) == 3

test_input = { "s1": "111101000111", "s2": "101111010010", "x": 16 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "0", "s2": "0", "x": 20 }
assert my_solution.minOperations(**test_input) == 0

test_input = { "s1": "0011111100011", "s2": "1001100101000", "x": 26 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "1000101111101001", "s2": "0110000010110010", "x": 25 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "11000010000", "s2": "11111000001", "x": 17 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "1110111001000001", "s2": "0110011110101101", "x": 1 }
assert my_solution.minOperations(**test_input) == 4

test_input = { "s1": "0111101101", "s2": "0000111001", "x": 2 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "000001110", "s2": "000101001", "x": 22 }
assert my_solution.minOperations(**test_input) == 4

test_input = { "s1": "1110000000", "s2": "1100111100", "x": 5 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "1101101010", "s2": "0101010011", "x": 15 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "0010011011000101001", "s2": "1110101001110100010", "x": 19 }
assert my_solution.minOperations(**test_input) == 9

test_input = { "s1": "11010011101011110111", "s2": "11101111011010010011", "x": 8 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "101100010", "s2": "100011110", "x": 29 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "00100001", "s2": "10011101", "x": 29 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "111111110110010", "s2": "111011111010001", "x": 29 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "11011110110010", "s2": "01010100000111", "x": 9 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "011101010101", "s2": "111001010100", "x": 19 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "00001", "s2": "11111", "x": 27 }
assert my_solution.minOperations(**test_input) == 2

test_input = { "s1": "110", "s2": "101", "x": 15 }
assert my_solution.minOperations(**test_input) == 1

test_input = { "s1": "11011001111000111001", "s2": "11100011111011110001", "x": 12 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "1010100", "s2": "0100111", "x": 2 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "000", "s2": "010", "x": 21 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "1011010100111101", "s2": "1010001100110110", "x": 18 }
assert my_solution.minOperations(**test_input) == 9

test_input = { "s1": "111", "s2": "000", "x": 4 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "00101100110110010", "s2": "00001111111011011", "x": 22 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "000110011", "s2": "010010001", "x": 8 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "1011000000", "s2": "0001010010", "x": 16 }
assert my_solution.minOperations(**test_input) == 5

test_input = { "s1": "01101100110011011011", "s2": "10101101010011001011", "x": 5 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "00010", "s2": "00011", "x": 8 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "1010110111000111", "s2": "1110110001001000", "x": 22 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "011110100000", "s2": "101100010100", "x": 21 }
assert my_solution.minOperations(**test_input) == 5

test_input = { "s1": "1011010010100101101", "s2": "1001001110101100000", "x": 29 }
assert my_solution.minOperations(**test_input) == 9

test_input = { "s1": "1111100", "s2": "0010100", "x": 20 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "0100100110001", "s2": "1001111110001", "x": 4 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "110", "s2": "011", "x": 2 }
assert my_solution.minOperations(**test_input) == 2

test_input = { "s1": "111111010101", "s2": "000011101101", "x": 30 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "101111110110010100", "s2": "010001111100000100", "x": 3 }
assert my_solution.minOperations(**test_input) == 7

test_input = { "s1": "0110111", "s2": "0111010", "x": 19 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "1101010101", "s2": "1011000110", "x": 14 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "01100101", "s2": "11010111", "x": 17 }
assert my_solution.minOperations(**test_input) == 5

test_input = { "s1": "0011111", "s2": "0110101", "x": 13 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "11110110111111011", "s2": "11101101111010110", "x": 19 }
assert my_solution.minOperations(**test_input) == 6

test_input = { "s1": "110100", "s2": "000011", "x": 20 }
assert my_solution.minOperations(**test_input) == -1

test_input = { "s1": "0101", "s2": "0010", "x": 29 }
assert my_solution.minOperations(**test_input) == -1