2896 Apply Operations to Make Two Strings Equal Solution

The 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 = "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'.

Approach overview

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.

Approach 1: Greedy Pair Matching

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.

Python

def min_cost_to_make_equal(s1, s2, x):
    n = len(s1)
    cost = 0
    i = 0
    while i < n:
        if s1[i] != s2[i]:
            if i + 1 < n and s1[i+1] != s2[i+1]:
                cost += 1
                i += 1
            else:
                cost += x
        i += 1
    return cost if i == n else -1

print(min_cost_to_make_equal("1100011000", "0101001010", 2))
print(min_cost_to_make_equal("10110", "00011", 4))

Java

public class Solution {
    public int minCostToMakeEqual(String s1, String s2, int x) {
        int n = s1.length();
        int cost = 0;
        for (int i = 0; i < n; i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                if (i + 1 < n && s1.charAt(i + 1) != s2.charAt(i + 1)) {
                    cost += 1;
                    i++; // Skip the next because it's compensated
                } else if (i + 1 < n) {
                    cost += x;
                } else {
                    return -1;
                }
            }
        }
        return cost;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minCostToMakeEqual("1100011000", "0101001010", 2)); 
        System.out.println(sol.minCostToMakeEqual("10110", "00011", 4)); 
    }
}

C++

#include <iostream>
#include <string>

int minCostToMakeEqual(const std::string& s1, const std::string& s2, int x) {
    int n = s1.size();
    int cost = 0;
    for (int i = 0; i < n; ++i) {
        if (s1[i] != s2[i]) {
            if (i + 1 < n && s1[i + 1] != s2[i + 1]) {
                cost += 1;
                ++i;
            } else if (i + 1 < n) {
                cost += x;
            } else {
                return -1;
            }
        }
    }
    return cost;
}

int main() {
    std::cout << minCostToMakeEqual("1100011000", "0101001010", 2) << std::endl;
    std::cout << minCostToMakeEqual("10110", "00011", 4) << std::endl;
    return 0;
}

JavaScript

function minCostToMakeEqual(s1, s2, x) {
    let n = s1.length;
    let cost = 0;
    for (let i = 0; i < n; i++) {
        if (s1[i] !== s2[i]) {
            if (i + 1 < n && s1[i + 1] !== s2[i + 1]) {
                cost += 1;
                i++;
            } else {
                cost += x;
            }
        }
    }
    return cost;
}

console.log(minCostToMakeEqual("1100011000", "0101001010", 2));
console.log(minCostToMakeEqual("10110", "00011", 4));

#include <stdio.h>
#include <string.h>

int minCostToMakeEqual(char* s1, char* s2, int x) {
    int n = strlen(s1);
    int cost = 0;
    int i = 0;

    while (i < n) {
        if (s1[i] != s2[i]) {
            if (i + 1 < n && s1[i + 1] != s2[i + 1]) {
                cost += 1; // Flipping adjacent
                i += 1;
            } else if (i + 1 < n) {
                cost += x; // Arbitrary pair flip
            } else {
                return -1; // It's impossible
            }
        }
        i += 1;
    }
    return cost;
}

int main() {
    printf("%d\n", minCostToMakeEqual("1100011000", "0101001010", 2)); 
    printf("%d\n", minCostToMakeEqual("10110", "00011", 4)); 
    return 0;
}

using System;

public class Solution {
    public int MinCostToMakeEqual(string s1, string s2, int x) {
        int n = s1.Length;
        int cost = 0;

        for (int i = 0; i < n; ++i) {
            if (s1[i] != s2[i]) {
                if (i + 1 < n && s1[i + 1] != s2[i + 1]) {
                    cost += 1;
                    i++; 
                } else if (i + 1 < n) {
                    cost += x;
                } else {
                    return -1;
                }
            }
        }
        return cost;
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.MinCostToMakeEqual("1100011000", "0101001010", 2));
        Console.WriteLine(sol.MinCostToMakeEqual("10110", "00011", 4));
    }
}

The function iteratively checks each mismatched point, attempting to resolve each one with minimal cost by making strategic flips locally wherever possible. This tactic reduces function time by leveraging local adjustments before resorting to full-scale corrections.

Complexity

Time Complexity: O(n) processes each character in an efficient one-time loop.
Space Complexity: O(1) extra space used during the procedure.

Try this approach in the editor

Approach 2: Dynamic Programming Optimization

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.

Python

def min_cost_to_make_equal(s1, s2, x):
    n = len(s1)
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        if s1[i - 1] == s2[i - 1]:
            dp[i] = dp[i - 1]
        else:
            cost1 = dp[i - 2] + 1 if i > 1 and s1[i - 2] != s2[i - 2] else float('inf')
            cost2 = dp[i - 1] + x
            dp[i] = min(cost1, cost2)
    return -1 if dp[n] == float('inf') else dp[n]

print(min_cost_to_make_equal("1100011000", "0101001010", 2))
print(min_cost_to_make_equal("10110", "00011", 4))

Java

public class Solution {
    public int minCostToMakeEqual(String s1, String s2, int x) {
        int n = s1.length();
        int[] dp = new int[n+1];
        for (int i = 1; i <= n; i++) {
            if (s1.charAt(i-1) == s2.charAt(i-1)) {
                dp[i] = dp[i-1];
            } else {
                int cost1 = (i > 1 && s1.charAt(i-2) != s2.charAt(i-2)) ? dp[i-2] + 1 : Integer.MAX_VALUE;
                int cost2 = dp[i-1] + x;
                dp[i] = Math.min(cost1, cost2);
            }
        }
        return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minCostToMakeEqual("1100011000", "0101001010", 2));
        System.out.println(sol.minCostToMakeEqual("10110", "00011", 4));
    }
}

C++

#include <iostream>
#include <vector>
#include <climits>

int minCostToMakeEqual(const std::string& s1, const std::string& s2, int x) {
    int n = s1.size();
    std::vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        if (s1[i - 1] == s2[i - 1]) {
            dp[i] = dp[i - 1];
        } else {
            int cost1 = (i > 1 && s1[i - 2] != s2[i - 2]) ? dp[i - 2] + 1 : INT_MAX;
            int cost2 = dp[i - 1] + x;
            dp[i] = std::min(cost1, cost2);
        }
    }
    return dp[n] == INT_MAX ? -1 : dp[n];
}

int main() {
    std::cout << minCostToMakeEqual("1100011000", "0101001010", 2) << std::endl;
    std::cout << minCostToMakeEqual("10110", "00011", 4) << std::endl;
    return 0;
}

JavaScript

function minCostToMakeEqual(s1, s2, x) {
    const n = s1.length;
    const dp = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        if (s1[i - 1] === s2[i - 1]) {
            dp[i] = dp[i - 1];
        } else {
            const cost1 = (i > 1 && s1[i - 2] !== s2[i - 2]) ? dp[i - 2] + 1 : Infinity;
            const cost2 = dp[i - 1] + x;
            dp[i] = Math.min(cost1, cost2);
        }
    }
    return dp[n] === Infinity ? -1 : dp[n];
}

console.log(minCostToMakeEqual("1100011000", "0101001010", 2));
console.log(minCostToMakeEqual("10110", "00011", 4));

#include <stdio.h>
#include <string.h>
#include <limits.h>

int minCostToMakeEqual(char* s1, char* s2, int x) {
    int n = strlen(s1);
    int dp[n+1];
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        if (s1[i-1] == s2[i-1]) {
            dp[i] = dp[i-1];
        } else {
            int cost1 = (i > 1 && s1[i-2] != s2[i-2]) ? dp[i-2] + 1 : INT_MAX;
            int cost2 = dp[i-1] + x;
            dp[i] = (cost1 < cost2) ? cost1 : cost2;
        }
    }
    return dp[n];
}

int main() {
    printf("%d\n", minCostToMakeEqual("1100011000", "0101001010", 2)); 
    printf("%d\n", minCostToMakeEqual("10110", "00011", 4)); 
    return 0;
}

using System;

public class Solution {
    public int MinCostToMakeEqual(string s1, string s2, int x) {
        int n = s1.Length;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            if (s1[i - 1] == s2[i - 1]) {
                dp[i] = dp[i - 1];
            } else {
                int cost1 = (i > 1 && s1[i - 2] != s2[i - 2]) ? dp[i - 2] + 1 : int.MaxValue;
                int cost2 = dp[i - 1] + x;
                dp[i] = Math.Min(cost1, cost2);
            }
        }
        return dp[n] == int.MaxValue ? -1 : dp[n];
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.MinCostToMakeEqual("1100011000", "0101001010", 2));
        Console.WriteLine(sol.MinCostToMakeEqual("10110", "00011", 4));
    }
}

This Python buildup clarifies DP's cumulative exchange of benefit prioritizing strategies. Successive calculations align precedents via retrospective data, easing future mapping despite inherently complex interactions and mappings.

Complexity

Time Complexity: O(n) - Direct interaction handling directly with string contents.
Space Complexity: O(n), dedicated for computed minimal state memory details.

Try this approach in the editor

Approach 3: Memoization

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]:

If we perform the first operation on endpoint 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.
If we perform the second operation on endpoint 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].
If we perform the second operation on endpoint 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.

TypeScript

function minOperations(s1: string, s2: string, x: number): number {
    const idx: number[] = [];
    for (let i = 0; i < s1.length; ++i) {
        if (s1[i] !== s2[i]) {
            idx.push(i);
        }
    }
    const m = idx.length;
    if (m % 2 === 1) {
        return -1;
    }
    if (m === 0) {
        return 0;
    }
    const f: number[][] = Array.from({ length: m }, () => Array.from({ length: m }, () => -1));
    const dfs = (i: number, j: number): number => {
        if (i > j) {
            return 0;
        }
        if (f[i][j] !== -1) {
            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[i + 1] - idx[i]);
        f[i][j] = Math.min(f[i][j], dfs(i, j - 2) + idx[j] - idx[j - 1]);
        return f[i][j];
    };
    return dfs(0, m - 1);
}

func minOperations(s1 string, s2 string, x int) int {
	idx := []int{}
	for i := range s1 {
		if s1[i] != s2[i] {
			idx = append(idx, i)
		}
	}
	m := len(idx)
	if m&1 == 1 {
		return -1
	}
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, m)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i > j {
			return 0
		}
		if f[i][j] != -1 {
			return f[i][j]
		}
		f[i][j] = dfs(i+1, j-1) + x
		f[i][j] = min(f[i][j], dfs(i+2, j)+idx[i+1]-idx[i])
		f[i][j] = min(f[i][j], dfs(i, j-2)+idx[j]-idx[j-1])
		return f[i][j]
	}
	return dfs(0, m-1)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Pair Matching	Time Complexity: O(n) processes each character in an efficient one-time loop. Space Complexity: O(1) extra space used during the procedure.
Dynamic Programming Optimization	Time Complexity: O(n) - Direct interaction handling directly with string contents. Space Complexity: O(n), dedicated for computed minimal state memory details.
Memoization	–

Complexity analysis

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.

Frequently asked questions

Is Apply Operations to Make Two Strings Equal easy or hard?

Apply Operations to Make Two Strings Equal is rated Medium on LeetCode with an acceptance rate around 27%. The challenge lies in recognizing that only mismatch indices matter and modeling the pairing decisions correctly using greedy reasoning or dynamic programming.

Apply Operations to Make Two Strings Equal Python/Java solution

Python, Java, C++, C#, and JavaScript implementations follow the same logic: gather mismatch indices, verify the count is even, and compute the minimum pairing cost using greedy or dynamic programming. The algorithm remains O(n) regardless of the language used.

How to solve Apply Operations to Make Two Strings Equal in O(n)?

First collect indices where s1[i] != s2[i]. If the mismatch count is odd, return -1. Otherwise process the mismatch list and pair indices while choosing the minimum cost between using the fixed operation cost x or resolving them through adjacent operations with cost equal to their distance. This yields an O(n) solution.

What is the best approach for Apply Operations to Make Two Strings Equal?

The optimal approach uses dynamic programming over the indices where the two strings differ. By storing mismatch positions and computing the minimum cost to resolve them pairwise, the DP ensures the globally minimal cost. The solution runs in O(n) time with O(n) space where n is the string length.

Is Apply Operations to Make Two Strings Equal asked at Google/Amazon/Meta?

Problems involving string transformations, mismatch pairing, and dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests the ability to reduce a string problem into a mismatch pairing optimization and model it using DP.

What data structure is used in Apply Operations to Make Two Strings Equal?

The core structure is an array or list that stores indices where the two strings differ. This mismatch list allows pairing decisions to be evaluated efficiently. Dynamic programming arrays are also used to compute the minimum cost for resolving mismatches.

What is the time complexity of Apply Operations to Make Two Strings Equal?

Both the greedy and dynamic programming solutions run in O(n) time because the strings are scanned once to collect mismatches and processed linearly afterward. Space complexity is O(n) due to storing mismatch indices or DP states.

Apply Operations to Make Two Strings Equal solution and explanation

The problem

Approach overview

Approach 1: Greedy Pair Matching

Approach 2: Dynamic Programming Optimization

Approach 3: Memoization

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Apply Operations to Make Two Strings Equal solution and explanation

The problem

Approach overview

Approach 1: Greedy Pair Matching

Approach 2: Dynamic Programming Optimization

Approach 3: Memoization

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems