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:
i and j, and flip both s1[i] and s1[j]. The cost of this operation is x.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.length1 <= n, x <= 500s1 and s2 consist only of the characters '0' and '1'.Problem Overview: You are given two binary strings s1 and s2 and a cost x. The goal is to transform s1 so it becomes identical to s2 using the minimum total cost. Only certain operations are allowed, and each operation can fix mismatched bits at specific positions.
The key observation: only indices where s1[i] != s2[i] matter. If the number of mismatches is odd, making the strings equal is impossible because every operation effectively resolves two mismatched bits.
Approach 1: Greedy Pair Matching (O(n) time, O(n) space)
First collect all indices where the characters differ. Each mismatch must be paired with another mismatch to fix both positions. For two mismatches at positions i and j, you have two choices: resolve them using adjacent operations that propagate a fix across the string (cost proportional to j - i), or directly resolve them using a special operation costing x. The optimal cost for that pair is min(x, j - i). A greedy strategy pairs nearby mismatches as you iterate through the mismatch list. This works well because pairing closer indices minimizes propagation cost while still allowing the constant-cost option when distance becomes expensive.
This approach scans the string once, records mismatch positions, and processes them sequentially. It runs in O(n) time and uses O(n) extra space for the mismatch list. It relies heavily on properties of string comparisons and local pairing decisions.
Approach 2: Dynamic Programming Optimization (O(n) time, O(n) space)
Greedy pairing does not always capture every optimal configuration when multiple pairing combinations exist. A more robust strategy uses dynamic programming over the mismatch indices. Let dp[i] represent the minimum cost to resolve the first i mismatches. For each step, you decide whether to pair mismatch i with i-1 using propagation cost (pos[i] - pos[i-1]), or handle it using the constant operation cost x. The recurrence chooses the minimum of these choices.
This DP effectively models all valid pairing configurations while still processing the mismatch array linearly. Time complexity remains O(n) and space complexity is O(n), where n is the string length (or the mismatch count). The approach guarantees the global minimum cost even when greedy decisions conflict.
Recommended for interviews: Start by explaining the mismatch observation and why the count must be even. Mention the greedy pairing intuition first since it shows you understand the structure of the operations. Then move to the dynamic programming formulation, which interviewers typically expect for correctness in edge cases. Demonstrating both approaches shows strong reasoning about pairing strategies and cost minimization in string transformations using dynamic programming.
This approach focuses on matching pairs of mismatched characters with minimum cost. By examining consecutive mismatched pairs, you can decide to use the single adjacent operation versus the more expensive arbitrary pair operation.
Identify mismatches between s1 and s2 and try to resolve these using the cheapest possible combinations of operations.
This function walks through the two strings simultaneously, flipping pairs as it encounters mismatches to resolve at the minimum cost. It adds to total cost the operation prices depending on whether adjacent or any arbitrary pair flip was done.
Time Complexity: O(n) since we iterate through the string once.
Space Complexity: O(1) as no additional space is used.
In this approach, we use a dynamic programming strategy to calculate the minimum cost necessary by analyzing the cost of moves at every point to create a comprehensive cost record. This helps in making optimized decisions about where to place operations.
Define a DP array where each entry represents the cost of resolving mismatches up to that specific point in the string. Eventually, the solution will rely on building up this DP table to extract the minimum total cost.
This DP approach employs a cost array, dp, to manage and calculate the minimal operability costs at sequential indices. By updating the DP table with combined previous data, calculation conflicts are resolved dynamically through an iterative and precise manner.
Time Complexity: O(n) - Linear based on the loop through every character.
Space Complexity: O(n) - DP table size is proportional to input length for storing operation details.
We notice that since each operation reverses two characters, if the number of different characters in the two strings is odd, it is impossible to make them equal, and we directly return -1. Otherwise, we store the indices of the different characters in the two strings in an array idx, and let m be the length of idx.
Next, we design a function dfs(i, j), which represents the minimum cost of reversing the characters in idx[i..j]. The answer is dfs(0, m - 1).
The calculation process of the function dfs(i, j) is as follows:
If i > j, we do not need to perform any operation, and return 0.
Otherwise, we consider the two endpoints of the interval [i, j]:
i, since the cost x is fixed, the optimal choice is to reverse idx[i] and idx[j], and then recursively calculate dfs(i + 1, j - 1), with a total cost of dfs(i + 1, j - 1) + x.i, we need to reverse all the characters in [idx[i]..idx[i + 1]], and then recursively calculate dfs(i + 2, j), with a total cost of dfs(i + 2, j) + idx[i + 1] - idx[i].j, we need to reverse all the characters in [idx[j - 1]..idx[j]], and then recursively calculate dfs(i, j - 2), with a total cost of dfs(i, j - 2) + idx[j] - idx[j - 1].We take the minimum value of the above three operations as the value of dfs(i, j).
To avoid redundant calculations, we can use memoization to record the return value of dfs(i, j) in a 2D array f. If f[i][j] is not equal to -1, it means that we have already calculated it, so we can directly return f[i][j].
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the strings.
Python
Java
C++
Go
TypeScript
Java
| Approach | Complexity |
|---|---|
| Greedy Pair Matching | Time Complexity: O(n) since we iterate through the string once. |
| Dynamic Programming Optimization | Time Complexity: O(n) - Linear based on the loop through every character. |
| Memoization | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Pair Matching | O(n) | O(n) | When mismatches can be paired locally and distance-based cost decisions are straightforward. |
| Dynamic Programming Optimization | O(n) | O(n) | General case where multiple pairing combinations exist and you need guaranteed minimal cost. |
2896. Apply Operations to Make Two Strings Equal | Weekly Leetcode 366 • codingMohan • 3,253 views views
Watch 9 more video solutions →Practice Apply Operations to Make Two Strings Equal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor