# Apply Operations to Make Two Strings Equal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/apply-operations-to-make-two-strings-equal)
Canonical: https://scaleengineer.com/dsa/problems/apply-operations-to-make-two-strings-equal
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Zeta](https://scaleengineer.com/companies/zeta)
---
## 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 _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 = "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:**

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

# Approaches
## Brute Force with Memoization (Bitmask DP)
This approach tackles the problem by exploring all possible ways to pair up the mismatching indices. After identifying the indices where `s1` and `s2` differ, we can see that to make them equal, we need to flip each of these positions. Since each operation flips two characters, the total number of differing characters must be even. If it's odd, we can immediately determine it's impossible.

The core of this method is a recursive function that systematically generates all perfect matchings of the mismatch indices. For each matching, it calculates the total cost and finds the minimum among them. To avoid recomputing results for the same subset of mismatches, we can use memoization with a bitmask, where the mask represents the set of mismatches yet to be paired. While correct, this approach is computationally expensive.
**Time:** O(2^k * k^2), where `k` is the number of mismatches. For each of the `2^k` states, we iterate up to `k^2` times to find two bits to pair. This is too slow for `k` up to 500. · **Space:** O(2^k), where `k` is the number of mismatches. This is for the memoization table.
**Pros:** Guaranteed to find the optimal solution.; Conceptually straightforward for those familiar with recursion and bitmask DP.
**Cons:** The time complexity is exponential, making it too slow for the given constraints where the number of mismatches `k` can be up to `n=500`.
### Explanation
Let's first find all indices where `s1[i] != s2[i]` and store them in a list `diffs`. The size of this list, `k`, must be even. If not, we return -1.

The problem then becomes finding the minimum cost to pair up all `k` indices. The cost of pairing `diffs[i]` and `diffs[j]` is `min(x, diffs[j] - diffs[i])`.

A recursive solution with memoization (a form of dynamic programming) can be used. We define a function `calculate(mask)` that computes the minimum cost to pair up the indices represented by the `1`s in the bitmask `mask`.

In the `calculate(mask)` function:
- If `mask` is 0, all mismatches are paired, so we return 0.
- If `dp[mask]` is already computed, return the stored value.
- Find the first mismatch to pair, say at index `i` (the first set bit in `mask`).
- Iterate through all other available mismatches `j` (other set bits in `mask`).
- For each `j`, calculate the cost of pairing `i` and `j`, and add it to the result of the recursive call for the remaining mismatches: `cost(i, j) + calculate(mask without i and j)`.
- The minimum of these values is the result for `dp[mask]`.

This approach explores all partitions into pairs, but its exponential nature makes it infeasible for larger inputs.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    private List<Integer> diffs;
    private int x;
    private int[] memo;

    public int minOperations(String s1, String s2, int x) {
        diffs = new ArrayList<>();
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diffs.add(i);
            }
        }

        if (diffs.size() % 2 != 0) {
            return -1;
        }
        if (diffs.isEmpty()) {
            return 0;
        }

        int k = diffs.size();
        memo = new int[1 << k];
        Arrays.fill(memo, -1);

        return solve((1 << k) - 1);
    }

    private int solve(int mask) {
        if (mask == 0) {
            return 0;
        }
        if (memo[mask] != -1) {
            return memo[mask];
        }

        int minCost = Integer.MAX_VALUE;
        
        // Find the first mismatch to pair
        int i = Integer.numberOfTrailingZeros(mask);
        int newMaskWithoutI = mask ^ (1 << i);

        // Find a mismatch to pair with i
        for (int j = i + 1; j < diffs.size(); j++) {
            if ((newMaskWithoutI & (1 << j)) != 0) {
                int cost = Math.min(x, diffs.get(j) - diffs.get(i));
                int remainingMask = newMaskWithoutI ^ (1 << j);
                int futureCost = solve(remainingMask);
                if (futureCost != Integer.MAX_VALUE) {
                    minCost = Math.min(minCost, cost + futureCost);
                }
            }
        }

        return memo[mask] = minCost;
    }
}
```
### Algorithm
1. First, identify all indices where `s1` and `s2` differ. Let's store these indices in a sorted list called `diffs`. Let `k` be the number of such indices.
2. If `k` is odd, it's impossible to make the strings equal because each operation flips two bits, maintaining the parity of mismatches. In this case, return -1.
3. If `k` is zero, the strings are already equal, so the cost is 0.
4. The problem is now to find a perfect matching on the `k` mismatch indices with minimum total weight, where the weight of an edge between index `i` and `j` is `min(x, diffs[j] - diffs[i])`.
5. A brute-force approach is to try every possible perfect matching. We can implement this with a recursive function, say `solve(mismatches_to_pair)`.
6. The base case for the recursion is when there are no mismatches left to pair; the cost is 0.
7. In the recursive step, pick the first mismatch `d1` from the set. Iterate through all other mismatches `d2` in the set and try pairing `(d1, d2)`.
8. For each choice, the cost is `min(x, d2 - d1)` plus the result of the recursive call on the remaining set of mismatches.
9. Return the minimum cost found among all choices for pairing `d1`.
10. To optimize this, we can use memoization or dynamic programming with a bitmask. The state `dp[mask]` would store the minimum cost to resolve the mismatches represented by the `mask`. A bit `i` being set in `mask` means the `i`-th mismatch has been paired.

## Dynamic Programming on Intervals
A more efficient method uses dynamic programming on intervals of the mismatch indices. The key insight is that the problem can be framed as finding a minimum weight perfect matching on the graph of mismatch indices, where edge weights are the costs of pairing. For this specific cost function (`min(x, distance)`), it can be shown that the optimal solution will not contain any 'crossing' pairings. For any four indices `i < j < k < l`, pairing `(i, k)` and `(j, l)` is never better than a non-crossing alternative like `(i, j)` and `(k, l)`.

This non-crossing property is crucial because it implies that if we pair an index `i` with an index `p`, all indices between `i` and `p` must be paired among themselves. This creates independent subproblems on contiguous intervals, which is a perfect setup for dynamic programming.

We can define `dp[i][j]` as the minimum cost to resolve all mismatches from index `i` to `j` in our list of differing indices. By iterating through all possible partners for the first index `i` in the interval, we can build up the solution from smaller subproblems to larger ones.
**Time:** O(k^3), where `k` is the number of mismatches. The three nested loops in the DP (or recursion depth and loop) give it a cubic complexity. For `k <= 500`, this might be on the edge of typical time limits but can pass. · **Space:** O(k^2), where `k` is the number of mismatches, for the memoization table.
**Pros:** Correct and guaranteed to find the optimal solution.; Much more efficient than the exponential brute-force approach.; Handles all cases correctly due to the proven non-crossing property.
**Cons:** The `O(k^3)` complexity might be slow if `k` is very close to the maximum `n`.; The DP formulation is non-trivial and can be tricky to implement correctly.
### Explanation
First, we find the indices where `s1` and `s2` differ and store them in a list `diffs`. Let `k` be the number of differences. If `k` is odd, it's impossible, so we return -1. If `k` is 0, the cost is 0.

We use a 2D array `dp[k][k]` for memoization, where `dp[i][j]` stores the minimum cost to resolve mismatches from `diffs[i]` to `diffs[j]`. We can implement this with a recursive function `solve(i, j)`.

- The function `solve(i, j)` calculates the minimum cost for the sub-array of mismatches `diffs[i...j]`.
- The base case: if `i > j`, the interval is empty, so the cost is 0.
- If `dp[i][j]` is already computed, we return its value.
- To compute `dp[i][j]`, we must pair the mismatch at `diffs[i]` with some other mismatch `diffs[p]` in the interval. Due to the non-crossing property, `p` must be such that `p-i` is odd. We iterate `p` from `i+1` to `j` with a step of 2.
- For each `p`, the total cost is the sum of three parts:
  1. The cost of pairing `diffs[i]` and `diffs[p]`: `min(x, diffs.get(p) - diffs.get(i))`.
  2. The minimum cost for the inner interval: `solve(i + 1, p - 1)`.
  3. The minimum cost for the remaining outer interval: `solve(p + 1, j)`.
- We take the minimum over all valid choices of `p`.
- The final answer is `solve(0, k-1)`.

This can also be implemented iteratively by looping over interval lengths.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    private List<Integer> diffs;
    private int x;
    private long[][] memo;

    public int minOperations(String s1, String s2, int x) {
        diffs = new ArrayList<>();
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diffs.add(i);
            }
        }

        int k = diffs.size();
        if (k % 2 != 0) {
            return -1;
        }
        if (k == 0) {
            return 0;
        }

        memo = new long[k][k];
        for (long[] row : memo) {
            Arrays.fill(row, -1);
        }

        return (int) solve(0, k - 1);
    }

    private long solve(int i, int j) {
        if (i >= j) {
            return 0;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }

        long minCost = Long.MAX_VALUE;

        // Option 1: Pair diffs[i] with diffs[i+1]
        minCost = Math.min(minCost, Math.min(x, diffs.get(i + 1) - diffs.get(i)) + solve(i + 2, j));

        // Option 2: Pair diffs[i] with diffs[j]
        minCost = Math.min(minCost, Math.min(x, diffs.get(j) - diffs.get(i)) + solve(i + 1, j - 1));
        
        // Option 3: Pair diffs[i] with some diffs[p] in between.
        // This is the general case which covers the above two and more.
        // The simplified logic below is sufficient and more efficient.
        // The full O(k^3) logic is pairing i with any valid p.
        // A more optimized O(k^2) DP is possible.
        // Let's use a simpler DP that is O(k^2)
        // dp[i] = min cost to fix first i mismatches
        // dp[i] = min(dp[i-2] + cost(i-1,i), dp[i-1] + x) -> this is not quite right.
        // The logic below is a common simplification that might not be fully correct for all cases
        // but is often a good heuristic. The full O(k^3) is safer.
        // Let's stick to the full O(k^3) logic for correctness.

        // Pair i with p
        for (int p = i + 1; p <= j; p += 2) {
            long currentCost = (long)Math.min(x, diffs.get(p) - diffs.get(i)) 
                               + solve(i + 1, p - 1) 
                               + solve(p + 1, j);
            minCost = Math.min(minCost, currentCost);
        }

        return memo[i][j] = minCost;
    }
}
```
*Note: The provided Java code implements the `O(k^3)` top-down DP. A careful analysis of the cost function might lead to an `O(k^2)` optimization, but the `O(k^3)` approach is a correct and standard way to solve problems with this non-crossing substructure.*
### Algorithm
1. Identify all indices where `s1` and `s2` differ and store them in a sorted list `diffs`. Let `k` be the number of mismatches.
2. If `k` is odd, return -1. If `k` is 0, return 0.
3. The problem is equivalent to a minimum weight perfect matching on the `k` indices. It can be proven that an optimal matching will not have 'crossing' pairs (i.e., pairing `i` with `k` and `j` with `l` for `i < j < k < l` is suboptimal). This property allows for a dynamic programming solution on intervals.
4. Let `dp[i][j]` be the minimum cost to resolve all mismatches in the sub-array `diffs[i...j]`.
5. We can compute `dp[i][j]` by iterating through all possible mismatches `p` that `diffs[i]` can be paired with. Due to the non-crossing property, `p` must be in `[i+1, j]` and the sub-array `diffs[i+1...p-1]` must be matched within itself, which means its length must be even. This implies `p-i` must be odd.
6. The DP recurrence relation is:
   `dp[i][j] = min_{p = i+1 to j, step 2} (cost(diffs[i], diffs[p]) + dp[i+1][p-1] + dp[p+1][j])`
   where `cost(a, b) = min(x, b - a)`.
7. The base case is `dp[i][i-1] = 0` (an empty interval has zero cost).
8. We can compute the DP table bottom-up by iterating over the length of the interval, `len`, from 2 to `k` in steps of 2.
9. The final answer is `dp[0][k-1]`.

# Solutions
### Java

```java
class Solution {
private
  List<Integer> idx = new ArrayList<>();
private
  Integer[][] f;
private
  int x;
public
  int minOperations(String s1, String s2, int x) {
    int n = s1.length();
    for (int i = 0; i < n; ++i) {
      if (s1.charAt(i) != s2.charAt(i)) {
        idx.add(i);
      }
    }
    int m = idx.size();
    if (m % 2 == 1) {
      return -1;
    }
    this.x = x;
    f = new Integer[m][m];
    return dfs(0, m - 1);
  }
private
  int dfs(int i, int j) {
    if (i > j) {
      return 0;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    f[i][j] = dfs(i + 1, j - 1) + x;
    f[i][j] = Math.min(f[i][j], dfs(i + 2, j) + idx.get(i + 1) - idx.get(i));
    f[i][j] = Math.min(f[i][j], dfs(i, j - 2) + idx.get(j) - idx.get(j - 1));
    return f[i][j];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minOperations(string s1, string s2, int x) {
    vector<int> idx;
    for (int i = 0; i < s1.size(); ++i) {
      if (s1[i] != s2[i]) {
        idx.push_back(i);
      }
    }
    int m = idx.size();
    if (m & 1) {
      return -1;
    }
    if (m == 0) {
      return 0;
    }
    int f[m][m];
    memset(f, -1, sizeof(f));
    function<int(int, int)> dfs = [&](int i, int j) {
      if (i > j) {
        return 0;
      }
      if (f[i][j] != -1) {
        return f[i][j];
      }
      f[i][j] = min({dfs(i + 1, j - 1) + x, dfs(i + 2, j) + idx[i + 1] - idx[i],
                     dfs(i, j - 2) + idx[j] - idx[j - 1]});
      return f[i][j];
    };
    return dfs(0, m - 1);
  }
};

```

### Python

```python
class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int: @ cache def dfs(i: int, j: int) -> int: if i > j: return 0 a = dfs(i + 1, j - 1) + x b = dfs(i + 2, j) + idx[i + 1] - idx[i] c = dfs(i, j - 2) + idx[j] - idx[j - 1] return min(a, b, c) n = len(s1) idx = [i for i in range(n) if s1[i] != s2[i]] m = len(idx) if m & 1: return - 1 return dfs(0, m - 1)

```