Apply Operations to Make Two Strings Equal — LeetCode 2896 Python Solution

The problem

You are given two 0-indexed binary strings s1 and s2, both of length n, and a positive integer x. You can perform any of the following operations on the string s1 any number of times: Choose two indices i and j, and flip both s1[i] and s1[j].

Example

Input

s1 = "1100011000", s2 = "0101001010", x = 2

Output

4

Explanation

We can do the following operations:

Python solution

class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i > j:
                return 0
            a = dfs(i + 1, j - 1) + x
            b = dfs(i + 2, j) + idx[i + 1] - idx[i]
            c = dfs(i, j - 2) + idx[j] - idx[j - 1]
            return min(a, b, c)

        n = len(s1)
        idx = [i for i in range(n) if s1[i] != s2[i]]
        m = len(idx)
        if m & 1:
            return -1
        return dfs(0, m - 1)

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2896. Apply Operations to Make Two Strings Equal is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems