Minimum cost to make two binary strings equal

String Greedy

38.8% acceptance

Mar 15, 2026

You are given two binary strings s and t, both of length n, and three positive integers flipCost, swapCost, and crossCost. Operations: flip a bit (flipCost), swap two positions in same string (swapCost), cross-swap s[i] with t[i] (crossCost). Return minimum total cost to make s and t equal.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_cost(s: String, t: String, flip_cost: i32, swap_cost: i32, cross_cost: i32) -> i64 {
    let sb = s.as_bytes();
    let tb = t.as_bytes();
    let mut count_a: i64 = 0; // s[i]=0, t[i]=1
    let mut count_b: i64 = 0; // s[i]=1, t[i]=0
    for i in 0..sb.len() {
      if sb[i] != tb[i] {
        if sb[i] == b'0' { count_a += 1; } else { count_b += 1; }
      }
    }
    let flip = flip_cost as i64;
    let swap = swap_cost as i64;
    let cross = cross_cost as i64;

    // Pair opposite types (A+B): swap within s fixes both at cost swapCost
    // Or fix individually: 2*flipCost
    let pairs_opp = count_a.min(count_b);
    let cost_per_opp = swap.min(2 * flip);

    // Remaining same-type pairs: cross-swap one to make it opposite, then swap
    // Cost: crossCost + swapCost, or fix individually: 2*flipCost
    let remaining = (count_a - count_b).abs();
    let pairs_same = remaining / 2;
    let leftover = remaining % 2;
    let cost_per_same = (cross + swap).min(2 * flip);

    pairs_opp * cost_per_opp + pairs_same * cost_per_same + leftover * flip
  }
}