Skip to content

3800. Minimum Cost to Make Two Binary Strings Equal

Description

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 <= 105​​​​​​​
  • 1 <= flipCost, swapCost, crossCost <= 109
  • s and t consist only of the characters '0' and '1'.

Solutions

Solution 1

Thinking

Only positions where \(s\) and \(t\) differ need work. With \(n \le 10^5\), searching operation sequences is infeasible.

Matching bits can stay as they are. Mismatches fall into two types: \(s[i]=\texttt{0}\) and \(t[i]=\texttt{1}\), or the reverse. Let their counts be \(d_0\) and \(d_1\).

A flip fixes any mismatch; an in-string swap pairs one type with the other; a cross swap changes the gap between the two counts. The optimum is therefore the cheapest among all-flips, pairing then flipping the leftover, and balancing with cross swaps before pairing.

We count the two mismatch types and compare those three closed-form costs, without simulating individual operations.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
}

Comments