Minimum ASCII Delete Sum for Two Strings

MediumDynamic Programming2d dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given two lowercase strings s1 and s2, you may delete characters from either string. Deleting a character costs its ASCII code (for example 'a' costs 97). Return the minimum total cost needed to make the two strings identical. Deleting every character of both strings is always allowed (both become empty), so an answer always exists.

Examples

Input: s1 = "sea", s2 = "eat"
Output: 231
Delete "s" (115) from s1 and "t" (116) from s2; both become "ea".
Input: s1 = "delete", s2 = "leet"
Output: 403
Keep "let": delete d, e, e from s1 (100+101+101) and e from s2 (101).

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More 2d dp problems