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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Minimum ASCII Delete Sum for Two Strings and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →