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
iandjand flip boths1[i]ands1[j]. This costsx. - Pick an index
i < n - 1and flip boths1[i]ands1[i + 1]. This costs1.
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.length1 <= n, x <= 500s1 and s2 consist only of '0' and '1'
Hints for Apply Operations to Make Two Strings Equal
Hint 1
Only the indices where the strings differ matter. Every operation flips two bits, so an odd number of mismatches is impossible.
Hint 2
Fixing two mismatches at positions
a < bcostsxwith one far flip, orb - awith a chain of adjacent flips. It never pays to chain two mismatches that are not neighbours in the list of mismatches.Hint 3
Let
dp[i]be the cost to fix the firstimismatches. Either thei-th one is chained to the(i-1)-th, or it is paired with some far mismatch — count that asx / 2per 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
- Collect the mismatch positions
p. If their count is odd, return -1; if zero, return 0. - Work with doubled costs:
dp[0] = 0,dp[1] = x(half ofx, doubled). - For
i ≥ 2:dp[i] = min(dp[i-1] + x, dp[i-2] + 2 · (p[i-1] - p[i-2])). - 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. xmay be odd: halving inside the DP loses precision, so double every cost and halve at the end.- When
xis 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 // 2Java
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