Skip to main content

712. Minimum ASCII Delete Sum for Two Strings

medium

Find the minimum sum of ASCII codes you must delete to make two strings equal. Weighted edit-distance variant — instead of counting deletions, you pay per character.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given two strings s1 and s2, return the lowest ASCII sum of deleted characters to make two strings equal.

Constraints

  • 1 <= s1.length, s2.length <= 1000
  • s1 and s2 consist of lowercase English letters.

Examples

Example 1

Input
s1 = "sea", s2 = "eat"
Output
231

Explanation: Deleting 's' from sea adds 115 to the sum; deleting 't' from eat adds 116. 115 + 116 = 231.

Example 2

Input
s1 = "delete", s2 = "leet"
Output
403

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

dp[i][j] = min ASCII delete sum to align s1[0..i-1] with s2[0..j-1].

Hint 2

Match: dp[i][j] = dp[i-1][j-1]. Mismatch: dp[i][j] = min(dp[i-1][j] + ascii(s1[i-1]), dp[i][j-1] + ascii(s2[j-1])).

Hint 3

Base: dp[i][0] = sum of ASCII codes of s1[0..i-1]; dp[0][j] = sum of ASCII codes of s2[0..j-1].

Solution approach

Reveal approach

Define the subproblem dp[i][j] = minimum ASCII delete sum to make s1[0..i-1] and s2[0..j-1] equal. The recurrence relation is dp[i][j] = dp[i-1][j-1] if s1[i-1] == s2[j-1] (free match), else dp[i][j] = min(dp[i-1][j] + ascii(s1[i-1]), dp[i][j-1] + ascii(s2[j-1])) — pay to delete one side or the other. Base cases dp[i][0] = prefix sum of s1's ASCII codes and dp[0][j] = prefix sum of s2's. Fill row by row and return dp[m][n]. Equivalent reformulation: maximize the ASCII sum of the common subsequence and subtract twice that from the total ASCII sum; both yield O(m * n) time and O(m * n) space, reducible to O(min(m, n)) with rolling rows.

Complexity

Time
O(m * n)
Space
O(m * n)

Related patterns

  • dynamic-programming
  • memoization-recursion
  • string-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

More Dynamic Programming practice problems

See all Dynamic Programming problems →