Tap here to switch tabs
Problem
Submissions

Problem: Minimum Cost to Make Two Binary Strings Equal

Minimum Cost to Make Two Binary Strings Equal gives two binary strings and costs for flips, adjacent swaps, and cross swaps. Find the least total cost to make the strings identical.

Statement

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

You can perform the following operations any number of times in any order:

  • Flip: Choose any character in s or t and flip it from '0' to '1' or from '1' to '0'. This operation costs flipCost.

  • Swap: Choose any two adjacent characters in s or in t and swap them. This operation costs swapCost.

  • Cross Swap: Choose an index i such that 0≤i<n0 \leq i < n, and swap s[i] with t[i]. This operation costs crossCost.

Return the minimum total cost required to make s equal to t.

Constraints:

  • n == s.length == t.length

  • 1≤n≤1051 \leq n \leq 10^5

  • 1≤1 \leq flipCost, swapCost, crossCost ≤109\leq 10^9

  • s and t consist only of the characters '0' and '1'.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimum Cost to Make Two Binary Strings Equal

Minimum Cost to Make Two Binary Strings Equal gives two binary strings and costs for flips, adjacent swaps, and cross swaps. Find the least total cost to make the strings identical.

Statement

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

You can perform the following operations any number of times in any order:

  • Flip: Choose any character in s or t and flip it from '0' to '1' or from '1' to '0'. This operation costs flipCost.

  • Swap: Choose any two adjacent characters in s or in t and swap them. This operation costs swapCost.

  • Cross Swap: Choose an index i such that 0≤i<n0 \leq i < n, and swap s[i] with t[i]. This operation costs crossCost.

Return the minimum total cost required to make s equal to t.

Constraints:

  • n == s.length == t.length

  • 1≤n≤1051 \leq n \leq 10^5

  • 1≤1 \leq flipCost, swapCost, crossCost ≤109\leq 10^9

  • s and t consist only of the characters '0' and '1'.