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

You may apply the following operations to the strings s and t any number of times, and in any order:

• Flip operation: Choose any index i and flip either s[i] or t[i] (change '0' to '1', or '1' to '0'). Each such operation costs flipCost.
• Swap operation (within a string): Choose two distinct indices i and j, then swap either s[i] and s[j], or t[i] and t[j]. Each such operation costs swapCost.
• Cross operation (across strings): Choose an index i and swap s[i] with t[i]. Each such operation costs crossCost.

Your goal is to make the two strings s and t equal using these operations.

Return an integer representing the minimum total cost required to make s and t equal.

The first thing to notice is that we only care about the positions i where s[i] != t[i]. Positions where s[i] == t[i] are already "equal" at that index and require no work. So our job reduces to fixing all the mismatched positions.

At any mismatched position, the pair (s[i], t[i]) is either (0, 1) or (1, 0). Let's classify them:

• diff[0] = number of positions where s[i] = 0 and t[i] = 1.
• diff[1] = number of positions where s[i] = 1 and t[i] = 0.

Now we think about how each operation helps us "cancel" these mismatches:

1. Flip alone. Every mismatched position can be fixed by a single flip (flip one of the two characters so they match). This costs flipCost per mismatch, giving a baseline answer of (diff[0] + diff[1]) * flipCost.

2. Pairing two mismatches of the same type using a swap. Here's the key insight: a swap within a single string (cost swapCost) can fix two mismatches of the same type at once. For example, if two positions both look like (0, 1), then in string s we have 0 and 0 and in t we have 1 and 1. By rearranging within one string, we can pair them up so both positions become matched after the right combination. So instead of paying 2 * flipCost for two same-type mismatches, we might pay swapCost for the pair. This is only worth it when swapCost < 2 * flipCost.

Since a swap pairs two same-type mismatches, the number of swaps we can do on one type is limited. Letting mn = min(diff) and mx = max(diff), the most natural plan is: use swaps on the smaller group as much as possible, then flip whatever is left. But within a single type, pairs come from the same group — so we pair up the smaller count mn of mismatches via swaps and flip the remaining mx - mn, giving mn * swapCost + (mx - mn) * flipCost.

3. Using cross operations to convert types. A cross operation (cost crossCost) swaps s[i] with t[i] at a single index, which turns a (0, 1) mismatch into a (1, 0) mismatch (or vice versa) — it changes the type of a mismatch without fixing it.

Why would that help? Because swaps can only pair up mismatches of the same type. If the two groups are unbalanced (mx much larger than mn), we can use cross operations to convert some of the larger group into the smaller type, balancing them so that more swaps become possible.

The ideal balance point is the average avg = (mx + mn) // 2. We spend (avg - mn) * crossCost to move mismatches from the larger group into the smaller until both groups are close to avg. Then we can do avg swaps (each canceling a same-type pair) costing avg * swapCost, and flip whatever odd leftover remains, costing (mx + mn - 2 * avg) * flipCost.

Putting it together. The three strategies above represent the meaningful ways to combine operations, and the answer is simply the minimum of these three candidate costs. The structure of the problem guarantees that mixing operations in any other way won't beat one of these clean strategies, because each operation type has a fixed role: flip fixes one mismatch, swap fixes a same-type pair, and cross rebalances types to enable more swaps.

Pattern Learn more about Greedy patterns.

We implement the three strategies described above and take their minimum. The whole process uses only simple counting and a few arithmetic comparisons — no advanced data structures are needed.

Step 1: Count the mismatches by type.

We create an array diff = [0, 0] to hold the counts of the two mismatch types. We then iterate over s and t together using zip(s, t). For each character pair (c1, c2):

• If c1 != c2, the position is mismatched. We increment diff[int(c1)].
  • diff[0] accumulates positions where s[i] = '0' (so t[i] = '1').
  • diff[1] accumulates positions where s[i] = '1' (so t[i] = '0').

diff = [0] * 2
for c1, c2 in zip(s, t):
    if c1 != c2:
        diff[int(c1)] += 1

Step 2: Baseline — flip everything.

Every mismatch can be fixed independently with one flip, so our starting candidate is:

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

Step 3: Compute mn and mx.

To reason about pairing, we identify the smaller and larger group sizes:

mx = max(diff)
mn = min(diff)

Step 4: Swap the smaller group, flip the rest.

A swap cancels a same-type pair. We can pair up mn mismatches via swaps and flip the remaining mx - mn:

ans = min(ans, mn * swapCost + (mx - mn) * flipCost)

We take min with the current ans so we only keep this strategy if it is cheaper than plain flipping.

Step 5: Cross to balance, then swap, then flip.

Cross operations convert one mismatch type into the other. We balance both groups toward the average:

avg = (mx + mn) // 2

The cost breaks into three parts:

• (avg - mn) * crossCost — convert mismatches from the larger group into the smaller until both reach about avg.
• avg * swapCost — perform avg swaps, each canceling a same-type pair.
• (mx + mn - avg * 2) * flipCost — flip the leftover (this is 0 when mx + mn is even, and 1 when it is odd, due to integer division).

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

Step 6: Return the result.

After evaluating all three candidate strategies and keeping the smallest, we return ans:

return ans

Complexity Analysis:

• Time complexity is O(n), where n is the length of the strings. We scan the strings once to count mismatches; the rest is constant-time arithmetic.
• Space complexity is O(1), since we only use the fixed-size diff array and a handful of scalar variables.