Problem statement

https://binarysearch.com/problems/Minimum-Digit-Delete/

Solution

It is variation of Leetcode 1143 Longest Common Subsequence, and Leetcode 0072. Edit Distance. Let dp[i][j] be the longest cost of common subsequence for a[:i+1] and b[:j+1]. We also add dummy zero in the beginning.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, a, b):
        a, b = "0" + a, "0" + b
        m, n = len(a), len(b)
        dp = [[0] * n for _ in range(m)]
        for i, j in product(range(m), range(n)):
            if i > 0:
                dp[i][j] = max(dp[i][j], dp[i-1][j])
            if j > 0:
                dp[i][j] = max(dp[i][j], dp[i][j-1])
            if i > 0 and j > 0 and a[i] == b[j]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-1] + int(a[i]))

        return sum(int(i) for i in a+b) - 2*dp[-1][-1]