3800. Minimum Cost to Make Two Binary Strings Equal - Solution

Q: Is Minimum Cost to Make Two Binary Strings Equal easy or hard?

The problem is usually rated Medium because the core logic is simple once the mismatch observation is made, but identifying the correct greedy pairing strategy can take time. Candidates often start with a brute force pairing idea before optimizing to the linear solution.

Q: Minimum Cost to Make Two Binary Strings Equal Python/Java solution

Implementations typically scan both strings, push mismatch indices into a list, and then apply the greedy pairing logic to accumulate the minimum cost. The same algorithm translates directly across Python, Java, C++, Go, and TypeScript because it only requires basic loops and arrays.

Q: How to solve Minimum Cost to Make Two Binary Strings Equal in O(n)?

First iterate through both strings and collect indices where the characters differ. Then process these mismatch indices in order while greedily deciding whether to pair the current mismatch with the previous one or resolve them separately. Each index is handled once, giving an O(n) time algorithm.

Q: What is the best approach for Minimum Cost to Make Two Binary Strings Equal?

The optimal approach uses a greedy strategy that processes all mismatch indices in order. By pairing nearby mismatches when it reduces the total operation cost, the algorithm minimizes the overall cost with a single linear pass. This reduces the time complexity to O(n) while using O(n) space to track mismatch positions.

Q: Is Minimum Cost to Make Two Binary Strings Equal asked at Google/Amazon/Meta?

Problems involving binary string transformations and minimum-cost operations frequently appear in interviews at companies like Amazon, Google, and Meta. They test greedy reasoning, string processing, and the ability to optimize from brute force to linear-time solutions.

Q: What data structure is used in Minimum Cost to Make Two Binary Strings Equal?

The main data structure is a simple array or list that stores indices where the two strings differ. This list allows the algorithm to process mismatches sequentially and apply greedy pairing decisions efficiently.

Q: What is the time complexity of Minimum Cost to Make Two Binary Strings Equal?

The optimal greedy solution runs in O(n) time where n is the length of the binary strings. Each index is checked once to detect mismatches, and the mismatch list is processed sequentially. Space complexity is O(n) in the worst case if every position differs.

The problem

You are given two binary strings s and t, both of length n, and three positive integers flipCost, swapCost, and crossCost.

You are allowed to apply the following operations any number of times (in any order) to the strings s and t:

Choose any index i and flip s[i] or t[i] (change '0' to '1' or '1' to '0'). The cost of this operation is flipCost.
Choose two distinct indices i and j, and swap either s[i] and s[j] or t[i] and t[j]. The cost of this operation is swapCost.
Choose an index i and swap s[i] with t[i]. The cost of this operation is crossCost.

Return an integer denoting the minimum total cost needed to make the strings s and t equal.

Example 1:

Input: s = "01000", t = "10111", flipCost = 10, swapCost = 2, crossCost = 2

Output: 16

Explanation:

We can perform the following operations:

Swap s[0] and s[1] (swapCost = 2). After this operation, s = "10000" and t = "10111".
Cross swap s[2] and t[2] (crossCost = 2). After this operation, s = "10100" and t = "10011".
Swap s[2] and s[3] (swapCost = 2). After this operation, s = "10010" and t = "10011".
Flip s[4] (flipCost = 10). After this operation, s = t = "10011".

The total cost is 2 + 2 + 2 + 10 = 16.

Example 2:

Input: s = "001", t = "110", flipCost = 2, swapCost = 100, crossCost = 100

Output: 6

Explanation:

Flipping all the bits of s makes the strings equal, and the total cost is 3 * flipCost = 3 * 2 = 6.

Example 3:

Input: s = "1010", t = "1010", flipCost = 5, swapCost = 5, crossCost = 5

Output: 0

Explanation:

The strings are already equal, so no operations are required.

Constraints:

n == s.length == t.length
1 <= n <= 10⁵
1 <= flipCost, swapCost, crossCost <= 10⁹
s and t consist only of the characters '0' and '1'.

Approach overview

Problem Overview: You are given two binary strings of equal length. Some positions differ. The task is to perform operations with a defined cost to resolve these mismatches so both strings become identical while minimizing the total cost.

Approach 1: Brute Force Pairing of Mismatches (O(n^2) time, O(n) space)

Start by scanning both strings and recording every index i where s[i] != t[i]. These are the positions that must be fixed. A brute force strategy tries pairing mismatches in every possible way and computes the cost for each pairing combination. This works because resolving two mismatches together can sometimes be cheaper than fixing them independently. The drawback is the combinatorial explosion: evaluating many pairing possibilities leads to O(n^2) time or worse when the mismatch count grows.

Approach 2: Greedy Pairing of Adjacent Mismatches (O(n) time, O(n) space)

The key observation: only the indices where the strings differ matter. Store all mismatch indices in an array while iterating once through the strings. Instead of exploring every pairing, process mismatches in order and greedily pair nearby ones when doing so reduces the total cost. The greedy rule works because pairing closer mismatches minimizes the operation cost compared to resolving them independently. This reduces the decision at each step to a simple local comparison, resulting in a linear pass through the mismatch list.

This approach relies heavily on sequential processing of indices and careful cost comparison. You iterate through the mismatch positions, evaluate whether combining the current mismatch with the previous unresolved one is cheaper than fixing both separately, and accumulate the minimum cost.

The algorithm is fundamentally a greedy strategy operating on mismatch positions discovered through a single scan of the string. Because each index is processed at most once, the runtime stays linear and memory usage remains small.

Recommended for interviews: The greedy linear scan is the solution interviewers expect. Showing the brute force pairing demonstrates you understand that mismatches must be paired or fixed individually. Transitioning to the greedy observation—processing mismatches in order and minimizing cost locally—shows the optimization step and strong algorithmic reasoning.

Solution

Python

class Solution:
    def minimumCost(
        self, s: str, t: str, flipCost: int, swapCost: int, crossCost: int
    ) -> int:
        diff = [0] * 2
        for c1, c2 in zip(s, t):
            if c1 != c2:
                diff[int(c1)] += 1
        ans = (diff[0] + diff[1]) * flipCost
        mx = max(diff)
        mn = min(diff)
        ans = min(ans, mn * swapCost + (mx - mn) * flipCost)
        avg = (mx + mn) // 2
        ans = min(
            ans,
            (avg - mn) * crossCost + avg * swapCost + (mx + mn - avg * 2) * flipCost,
        )
        return ans

Java

class Solution {
    public long minimumCost(String s, String t, int flipCost, int swapCost, int crossCost) {
        long[] diff = new long[2];
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c1 = s.charAt(i), c2 = t.charAt(i);
            if (c1 != c2) {
                diff[c1 - '0']++;
            }
        }

        long ans = (diff[0] + diff[1]) * flipCost;

        long mx = Math.max(diff[0], diff[1]);
        long mn = Math.min(diff[0], diff[1]);
        ans = Math.min(ans, mn * swapCost + (mx - mn) * flipCost);

        long avg = (mx + mn) / 2;
        ans = Math.min(
            ans, (avg - mn) * crossCost + avg * swapCost + (mx + mn - avg * 2) * flipCost);
        return ans;
    }
}

C++

class Solution {
public:
    long long minimumCost(string s, string t, int flipCost, int swapCost, int crossCost) {
        long long diff[2] = {0, 0};
        int n = s.size();
        for (int i = 0; i < n; i++) {
            if (s[i] != t[i]) {
                diff[s[i] - '0']++;
            }
        }

        long long ans = (diff[0] + diff[1]) * flipCost;

        long long mx = max(diff[0], diff[1]);
        long long mn = min(diff[0], diff[1]);
        ans = min(ans, mn * 1LL * swapCost + (mx - mn) * flipCost);

        long long avg = (mx + mn) / 2;
        ans = min(ans, (avg - mn) * crossCost + avg * swapCost + (mx + mn - avg * 2) * flipCost);

        return ans;
    }
};

TypeScript

function minimumCost(
    s: string,
    t: string,
    flipCost: number,
    swapCost: number,
    crossCost: number,
): number {
    const diff: number[] = [0, 0];
    const n = s.length;

    for (let i = 0; i < n; i++) {
        if (s[i] !== t[i]) {
            diff[s.charCodeAt(i) - 48]++;
        }
    }

    let ans = (diff[0] + diff[1]) * flipCost;

    const mx = Math.max(diff[0], diff[1]);
    const mn = Math.min(diff[0], diff[1]);
    ans = Math.min(ans, mn * swapCost + (mx - mn) * flipCost);

    const avg = (mx + mn) >> 1;
    ans = Math.min(ans, (avg - mn) * crossCost + avg * swapCost + (mx + mn - avg * 2) * flipCost);

    return ans;
}

func minimumCost(s string, t string, flipCost int, swapCost int, crossCost int) int64 {
	var diff [2]int64
	n := len(s)
	for i := 0; i < n; i++ {
		if s[i] != t[i] {
			diff[s[i]-'0']++
		}
	}

	ans := (diff[0] + diff[1]) * int64(flipCost)

	mx := max(diff[0], diff[1])
	mn := min(diff[0], diff[1])
	ans = min(ans, mn*int64(swapCost)+(mx-mn)*int64(flipCost))

	avg := (mx + mn) / 2
	ans = min(ans, (avg-mn)*int64(crossCost)+avg*int64(swapCost)+(mx+mn-avg*2)*int64(flipCost))

	return ans
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Mismatch Pairing	O(n^2)	O(n)	Useful for understanding the pairing idea and validating smaller inputs
Greedy Pairing of Mismatches	O(n)	O(n)	Best general solution for large strings and interview settings

Frequently asked questions

Is Minimum Cost to Make Two Binary Strings Equal easy or hard?

The problem is usually rated Medium because the core logic is simple once the mismatch observation is made, but identifying the correct greedy pairing strategy can take time. Candidates often start with a brute force pairing idea before optimizing to the linear solution.

Minimum Cost to Make Two Binary Strings Equal Python/Java solution

Implementations typically scan both strings, push mismatch indices into a list, and then apply the greedy pairing logic to accumulate the minimum cost. The same algorithm translates directly across Python, Java, C++, Go, and TypeScript because it only requires basic loops and arrays.

How to solve Minimum Cost to Make Two Binary Strings Equal in O(n)?

First iterate through both strings and collect indices where the characters differ. Then process these mismatch indices in order while greedily deciding whether to pair the current mismatch with the previous one or resolve them separately. Each index is handled once, giving an O(n) time algorithm.

What is the best approach for Minimum Cost to Make Two Binary Strings Equal?

The optimal approach uses a greedy strategy that processes all mismatch indices in order. By pairing nearby mismatches when it reduces the total operation cost, the algorithm minimizes the overall cost with a single linear pass. This reduces the time complexity to O(n) while using O(n) space to track mismatch positions.

Is Minimum Cost to Make Two Binary Strings Equal asked at Google/Amazon/Meta?

Problems involving binary string transformations and minimum-cost operations frequently appear in interviews at companies like Amazon, Google, and Meta. They test greedy reasoning, string processing, and the ability to optimize from brute force to linear-time solutions.

What data structure is used in Minimum Cost to Make Two Binary Strings Equal?

The main data structure is a simple array or list that stores indices where the two strings differ. This list allows the algorithm to process mismatches sequentially and apply greedy pairing decisions efficiently.

What is the time complexity of Minimum Cost to Make Two Binary Strings Equal?

The optimal greedy solution runs in O(n) time where n is the length of the binary strings. Each index is checked once to detect mismatches, and the mismatch list is processed sequentially. Space complexity is O(n) in the worst case if every position differs.

Minimum Cost to Make Two Binary Strings Equal solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Minimum Cost to Make Two Binary Strings Equal solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems