LeetCode in Kotlin

3800. Minimum Cost to Make Two Binary Strings Equal

Medium

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'.

Solution

import kotlin.math.min

class Solution {
    fun minimumCost(s: String, t: String, flipCost: Int, swapCost: Int, crossCost: Int): Long {
        val len = t.length
        var diff = 0
        var one = 0
        var zero = 0
        val arr1 = s.toCharArray()
        val arr2 = t.toCharArray()
        for (i in 0..<len) {
            if (arr1[i] != arr2[i]) {
                diff++
                if (arr1[i] == '0') {
                    zero++
                } else {
                    one++
                }
            }
        }
        val min = min(one, zero)
        var ans: Long = 0
        val costOfFlip = (min.toLong() * flipCost) * 2
        val costOfSwap = (min.toLong() * swapCost)
        ans += min(costOfFlip, costOfSwap)
        diff -= (min * 2)
        val oddLeft = diff % 2
        val evenLeft = diff - oddLeft
        val costOfCrossSwap =
            (((evenLeft / 2).toLong() * crossCost) + ((evenLeft / 2).toLong() * swapCost))
        val costOfFlipMain = (evenLeft.toLong() * flipCost)
        ans += min(costOfCrossSwap, costOfFlipMain)
        ans += oddLeft.toLong() * flipCost
        return ans
    }
}

This site is open source. Improve this page.