Problem

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 _theminimum cost needed to make the strings _s1 ands2 equal, or return-1 if it is impossible.

Note that flipping a character means changing it from 0 to 1 or vice-versa.

Examples

Example 1

1
2
3
4
5
6
7

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 = "110 _**11**_ 11000".
- Choose i = 4 and apply the second operation. The resulting string is s1 = "1101** _00_** 1000".
- Choose i = 0 and j = 8 and apply the first operation. The resulting string is s1 = "_**0**_ 1010010 _**1**_ 0" = s2.
The total cost is 1 + 1 + 2 = 4. It can be shown that it is the minimum cost possible.

Example 2

1
2
3

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

Solution

Method 1 – Dynamic Programming with Greedy Pairing

Intuition

The key idea is to minimize the cost by pairing adjacent mismatches with the cheaper operation (cost 1), and use the more expensive operation (cost x) for remaining unpaired mismatches. If the number of mismatches is odd, it’s impossible.

Approach

  1. Identify all indices where s1[i] != s2[i].
  2. If the number of mismatches is odd, return -1.
  3. For each pair of adjacent mismatches, decide whether to use the adjacent flip (cost 1) or the general flip (cost x).
  4. Use dynamic programming to compute the minimum cost:
  • dp[i] = minimum cost to fix the first i mismatches.
  • For each mismatch, either pair it with the previous one (if adjacent) or use the general operation.
  1. Return the minimum cost for all mismatches.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
   int minOperations(string s1, string s2, int x) {
      int n = s1.size();
      vector<int> diff;
      for (int i = 0; i < n; ++i)
        if (s1[i] != s2[i]) diff.push_back(i);
      int m = diff.size();
      if (m % 2) return -1;
      vector<int> dp(m + 1, 1e9);
      dp[0] = 0;
      for (int i = 2; i <= m; ++i) {
        // Pair last two mismatches
        int cost = (diff[i-1] == diff[i-2] + 1) ? min(x, 1) : x;
        dp[i] = min(dp[i], dp[i-2] + cost);
      }
      return dp[m];
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
   public int minOperations(String s1, String s2, int x) {
      int n = s1.length();
      List<Integer> diff = new ArrayList<>();
      for (int i = 0; i < n; ++i)
        if (s1.charAt(i) != s2.charAt(i)) diff.add(i);
      int m = diff.size();
      if (m % 2 != 0) return -1;
      int[] dp = new int[m + 1];
      Arrays.fill(dp, Integer.MAX_VALUE / 2);
      dp[0] = 0;
      for (int i = 2; i <= m; ++i) {
        int cost = (diff.get(i-1) == diff.get(i-2) + 1) ? Math.min(x, 1) : x;
        dp[i] = Math.min(dp[i], dp[i-2] + cost);
      }
      return dp[m];
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
   def minOperations(self, s1: str, s2: str, x: int) -> int:
      n = len(s1)
      diff = [i for i in range(n) if s1[i] != s2[i]]
      m = len(diff)
      if m % 2:
        return -1
      dp = [float('inf')] * (m + 1)
      dp[0] = 0
      for i in range(2, m + 1):
        cost = x
        if diff[i-1] == diff[i-2] + 1:
           cost = min(x, 1)
        dp[i] = min(dp[i], dp[i-2] + cost)
      return dp[m]

Complexity

  • ⏰ Time complexity: O(N)
  • 🧺 Space complexity: O(N)