Problem Statement in English

You’re given two strings s1 and s2. You want to make these two strings equal by deleting some characters from either string. The cost of deleting a character is equal to its ASCII value.

Return the minimum cost to make the two strings equal.

Approach

We’re just going to have to try all possible ways of deleting characters from both strings until they become equal. This screams dynamic programming.

So for each index in both strings, we have two choices:

  1. If the characters at the current indices are equal, we move to the next indices in both strings.
  2. If the characters are not equal, we have two options:
    • Delete the character from s1 and add its ASCII value to the cost, then move to the next index in s1.
    • Delete the character from s2 and add its ASCII value to the cost, then move to the next index in s2.

The base cases will be when one of the strings is exhausted. In that case, we need to delete all remaining characters from the other string.

And that’s it!

Solution in Python


class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        M = len(s1)
        N = len(s2)
        
        @cache
        def dp(i, j):
            # if s1 is exhausted, delete rest of s2
            if i == M:
                return sum(ord(c) for c in s2[j:])
            # if s2 is exhausted, delete rest of s1
            if j == N:
                return sum(ord(c) for c in s1[i:])

            if s1[i] == s2[j]:
                return dp(i + 1, j + 1)
            else:
                return min(
                    ord(s1[i]) + dp(i + 1, j),
                    ord(s2[j]) + dp(i, j + 1),
                    )

        return dp(0, 0)

Complexity

  • Time: $O(M \times N)$
    Since we have M*N states and each state takes O(1) time.

  • Space: $O(M \times N)$
    Since the cache will store M*N states.

Mistakes I Made

I fumbled the base case.

And we are done.