Scale Engineer

Apply Operations to Make Two Strings Equal

Med
#2577Time: 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.1 company
Patterns
Dynamic Programming
Data structures
String
Companies
Zeta

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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 1s 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.

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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem