Minimum ASCII Delete Sum for Two Strings · Interview Problem

Back to problems

Leetcode

Medium

Strings

Dynamic Programming

DP on Strings

Google

Microsoft

Minimum ASCII Delete Sum for Two Strings

Delete characters from two strings so the remaining common subsequence has the minimum total ASCII deletion cost.

Acceptance 100%

Start Practice

Problem Statement

Problem

Given two strings s1 and s2, you may delete characters from either string. Each deleted character adds its ASCII value to the total cost.

Return the minimum possible total ASCII deletion sum needed to make the two strings equal.

Two strings are considered equal if they become exactly the same after deletions.

Notes

You may delete any number of characters from either string.
You do not need to preserve original positions beyond maintaining order among remaining characters.
The goal is to minimize the sum of ASCII values of all deleted characters.

Input Format

Two strings s1 and s2.

Output Format

A single integer: the minimum ASCII deletion sum required to make the strings equal.

Constraints

0 <= s1.length, s2.length <= 1000
Strings contain lowercase English letters in the common interview formulation.
The answer fits in a 32-bit signed integer for standard constraints.

Hints

Think about what characters can remain in both strings after deletions.
A dynamic programming table over prefixes can track the minimum cost to equalize suffixes or prefixes.
It can help to compare the cost of deleting from one side versus matching equal characters.

Input Format

s1: first string
s2: second string

Output Format

Return the minimum total ASCII deletion sum needed to make s1 and s2 equal.

Constraints

0 <= |s1|, |s2| <= 1000
Characters are typically lowercase letters in the standard problem setting.
Use 32-bit integer arithmetic for the final answer.

Examples

Sample cases returned by the problem API.

Example 1

Input

s1 = "sea", s2 = "eat"

Output

Explanation

Delete 's' from "sea" and 't' from "eat". The cost is 115 + 116 = 231.

Example 2

Input

s1 = "delete", s2 = "leet"

Output

Explanation

One optimal way is to delete 'd' and 'e' from the first string and 'l' from the second string, among other equivalent optimal choices, for a total cost of 403.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress