Apply Operations to Make Two Strings Equal

Medium
1640.

Apply Operations to Make Two Strings Equal

Apply Operations to Make Two Strings Equal is a medium coding problem on strings and dynamic programming, asked in Amazon and Google interviews.

You are given two binary strings s1 and s2 of the same length n, and a positive integer x. You may change s1 with these operations, any number of times:

  • Pick any two indices i and j and flip both s1[i] and s1[j]. This costs x.
  • Pick an index i < n - 1 and flip both s1[i] and s1[i + 1]. This costs 1.

Flipping turns 0 into 1 and 1 into 0.

Return the minimum total cost to make s1 equal to s2, or -1 if it cannot be done.

Example 1

Input
s1 = "1100011000", s2 = "0101001010", x = 2
Output
4
Explanation
The strings differ at indices 0, 3, 5 and 8. Flip indices 3 and 4 (cost 1), then 4 and 5 (cost 1) — that fixes 3 and 5. Pair 0 with 8 using the first operation (cost 2). Total 4.

Example 2

Input
s1 = "10110", s2 = "00011", x = 4
Output
-1
Explanation
They differ in three places. Every operation flips two bits, so the number of mismatches always changes by an even amount and can never reach zero.

Example 3

Input
s1 = "0110", s2 = "0110", x = 7
Output
0

Constraints

  • n == s1.length == s2.length
  • 1 <= n, x <= 500
  • s1 and s2 consist only of '0' and '1'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s1
 * @param {string} s2
 * @param {number} x
 * @return {number}
 */
var minOperations = function(s1, s2, x) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Apply Operations to Make Two Strings Equal — Solution

Apply Operations to Make Two Strings Equal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Apply Operations to Make Two Strings Equal is a medium coding problem on strings and dynamic programming, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Dynamic Programming
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given two binary strings s1 and s2 of the same length n, and a positive integer x. You may change s1 with these operations, any number of times:

  • Pick any two indices i and j and flip both s1[i] and s1[j]. This costs x.
  • Pick an index i < n - 1 and flip both s1[i] and s1[i + 1]. This costs 1.

Flipping turns 0 into 1 and 1 into 0.

Return the minimum total cost to make s1 equal to s2, or -1 if it cannot be done.

Example 1

Input: s1 = "1100011000", s2 = "0101001010", x = 2
Output: 4
Explanation: The strings differ at indices 0, 3, 5 and 8. Flip indices 3 and 4 (cost 1), then 4 and 5 (cost 1) — that fixes 3 and 5. Pair 0 with 8 using the first operation (cost 2). Total 4.

Example 2

Input: s1 = "10110", s2 = "00011", x = 4
Output: -1
Explanation: They differ in three places. Every operation flips two bits, so the number of mismatches always changes by an even amount and can never reach zero.

Example 3

Input: s1 = "0110", s2 = "0110", x = 7
Output: 0

Constraints

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

Hints for Apply Operations to Make Two Strings Equal

  1. Hint 1

    Only the indices where the strings differ matter. Every operation flips two bits, so an odd number of mismatches is impossible.

  2. Hint 2

    Fixing two mismatches at positions a < b costs x with one far flip, or b - a with a chain of adjacent flips. It never pays to chain two mismatches that are not neighbours in the list of mismatches.

  3. Hint 3

    Let dp[i] be the cost to fix the first i mismatches. Either the i-th one is chained to the (i-1)-th, or it is paired with some far mismatch — count that as x / 2 per endpoint (double every cost to keep integers).

How to solve Apply Operations to Make Two Strings Equal

Reduce the strings to the sorted list p of mismatch positions. Each mismatch is either chained to its neighbour in p (cost p[i] - p[i-1]) or matched with some other far mismatch for x, which is fair to charge as x / 2 to each of its two ends.

Approach

  1. Collect the mismatch positions p. If their count is odd, return -1; if zero, return 0.
  2. Work with doubled costs: dp[0] = 0, dp[1] = x (half of x, doubled).
  3. For i ≥ 2: dp[i] = min(dp[i-1] + x, dp[i-2] + 2 · (p[i-1] - p[i-2])).
  4. Return dp[m] / 2.

Why it works

The far operations pair up mismatches arbitrarily, so all that matters is which mismatches are fixed that way — an even number of them — and each costs x / 2. A chain between two mismatches costs their distance; an optimal solution only chains neighbours in p, because a chain from a to c past b can be uncrossed without raising the cost. The DP decides, left to right, whether the current mismatch closes a chain with the previous one or goes into the far pool.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Chaining adjacent flips between two mismatches flips every bit in between twice — it really costs b - a, not 1.
  • x may be odd: halving inside the DP loses precision, so double every cost and halve at the end.
  • When x is 1 or 2 the far operation can be cheaper than chaining even close neighbours.

Reference solution

Python

def minOperations(s1: str, s2: str, x: int) -> int:
    pos = [i for i in range(len(s1)) if s1[i] != s2[i]]
    if len(pos) % 2:
        return -1
    if not pos:
        return 0
    # Costs are doubled so a far pairing can be charged x/2 per mismatch.
    prev2, prev1 = 0, x
    for i in range(1, len(pos)):
        cur = min(prev1 + x, prev2 + 2 * (pos[i] - pos[i - 1]))
        prev2, prev1 = prev1, cur
    return prev1 // 2

Java

public static int minOperations(String s1, String s2, int x) {
    List<Integer> pos = new ArrayList<>();
    for (int i = 0; i < s1.length(); i++) if (s1.charAt(i) != s2.charAt(i)) pos.add(i);
    if (pos.size() % 2 == 1) return -1;
    if (pos.isEmpty()) return 0;
    // Costs are doubled so a far pairing can be charged x/2 per mismatch.
    int prev2 = 0, prev1 = x;
    for (int j = 1; j < pos.size(); j++) {
        int cur = Math.min(prev1 + x, prev2 + 2 * (pos.get(j) - pos.get(j - 1)));
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1 / 2;
}

C++

int minOperations(string s1, string s2, int x) {
    vector<int> pos;
    for (int i = 0; i < (int) s1.size(); i++) if (s1[i] != s2[i]) pos.push_back(i);
    if (pos.size() % 2 == 1) return -1;
    if (pos.empty()) return 0;
    // Costs are doubled so a far pairing can be charged x/2 per mismatch.
    int prev2 = 0, prev1 = x;
    for (int j = 1; j < (int) pos.size(); j++) {
        int cur = min(prev1 + x, prev2 + 2 * (pos[j] - pos[j - 1]));
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1 / 2;
}

JavaScript

var minOperations = function(s1, s2, x) {
    var pos = [];
    for (var i = 0; i < s1.length; i++) if (s1[i] !== s2[i]) pos.push(i);
    if (pos.length % 2 === 1) return -1;
    if (pos.length === 0) return 0;
    // Costs are doubled so a far pairing can be charged x/2 per mismatch.
    var prev2 = 0, prev1 = x;
    for (var j = 1; j < pos.length; j++) {
        var cur = Math.min(prev1 + x, prev2 + 2 * (pos[j] - pos[j - 1]));
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1 / 2;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming