Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Consider making two prefixes equal. Matching final characters can be kept together for free. If they differ, at least one must be deleted, so we choose between paying for the first string's final character and paying for the second's. The costs of the remaining prefixes are smaller instances of the same problem.

Approach

Define dp[i][j] as the minimum deletion cost for the first i characters of s1 and first j characters of s2.
Initialize an empty-prefix boundary with cumulative ASCII costs, since every character of the other prefix must be deleted.
If the final characters match, copy dp[i - 1][j - 1]. Otherwise, take the minimum of dp[i - 1][j] plus the first character's cost and dp[i][j - 1] plus the second's.
Fill prefixes in increasing order and return dp[n][m]. Costs, rather than the number of deletions, determine the optimal common remaining string.

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        n = len(s1)
        m = len(s2)
        dp = [[0] * (m + 1) for _ in range(n + 1)]

        for i in range(1, n + 1):
            dp[i][0] = dp[i - 1][0] + ord(s1[i - 1])

        for j in range(1, m + 1):
            dp[0][j] = dp[0][j - 1] + ord(s2[j - 1])

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                    # carry acc value
                else:
                    dp[i][j] = min(
                        dp[i - 1][j] + ord(s1[i - 1]),
                        # remove s1[i - 1]
                        dp[i][j - 1] + ord(s2[j - 1])
                        # remove s2[j - 1]
                    )

        return dp[-1][-1]

Complexity analysis

For lengths n = s1.length and m = s2.length, the DP fills (n + 1)(m + 1) states. Time and auxiliary space are both O(nm).