What is the brute force approach and complexity for Minimum ASCII Delete Sum for Two Strings?

Recurse on (i, j): keep a matching pair for free, or delete one of the last letters with time complexity O(3^(N + M)) and space complexity O(N + M).

What is the optimal approach and complexity for Minimum ASCII Delete Sum for Two Strings?

The same table in two rows: a cell only reads the row above and the cell to its left with optimal time complexity O(N · M) and space complexity O(M).

How do you identify the pattern for Minimum ASCII Delete Sum for Two Strings?

Look for key signals in the prompt: "make both strings equal" indicates The letters that stay form a common subsequence of both strings, so the question is about a common subsequence.; "delete characters only" indicates There is no replace and no insert, so each cell has two moves, not three.; "lowest ASCII sum of deleted characters" indicates Each letter has a weight, and deleting it costs its weight. The best answer keeps the heaviest common subsequence..

Minimum ASCII Delete Sum for Two Strings

Medium·LeetCode #712 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You get two strings, s1 and s2. Delete some letters from each string, so that the two strings end up equal.

Deleting a letter costs its ASCII code (for example, a costs 97). Return the smallest total cost of the letters you delete.

Input

Two strings s1 and s2.

Output

The lowest total ASCII value of the letters that must be deleted to make the two strings equal.

Example 1

Input: s1 = "sea", s2 = "eat"

Output: 231

Delete s (115) from sea and t (116) from eat. Both become ea, and 115 + 116 = 231. No other choice is cheaper.

Example 2

Input: s1 = "delete", s2 = "leet"

Output: 403

Delete d, e, e (100 + 101 + 101) from delete to get let, and delete one e (101) from leet. The total is 403. Making both strings equal to lee or eet costs more.

Constraints

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

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“make both strings equal”

→ The letters that stay form a common subsequence of both strings, so the question is about a common subsequence.

“delete characters only”

→ There is no replace and no insert, so each cell has two moves, not three.

“lowest ASCII sum of deleted characters”

→ Each letter has a weight, and deleting it costs its weight. The best answer keeps the heaviest common subsequence.

Approach Complexity Ladder

Brute Force — keep a matching pair, or delete one of the last lettersO(3^(N + M))O(N + M)

Recurse on (i, j): keep a matching pair for free, or delete one of the last letters

Better — 2D table over the prefixes of s1 and s2O(N · M)O(N · M)

dp[i][j] = lowest deletion cost for the first i and first j letters; each cell is filled once

Optimal — two rows, keep only the row aboveO(N · M)O(M)

The same table in two rows: a cell only reads the row above and the cell to its left

Brute Force Intuition

Let cost(i, j) be the lowest ASCII sum to delete so that the first i letters of s1 and the first j letters of s2 become equal. If the last letters match, we may keep both: cost(i − 1, j − 1). We can always delete the last letter of s1 (its code plus cost(i − 1, j)), or the last letter of s2 (its code plus cost(i, j − 1)). Take the cheapest option. When one prefix is empty, delete all of the other one.

Recognition rule for this sub-pattern:

Each cell picks the cheapest of insert / delete / replace (or the pattern rule for *, ?, .).

Remember this · DP — Strings

Trigger

Longest common subsequence, edit distance, palindromes, matching with wildcards, interleaving.

Think

Look at the last characters: if they match, what do I do? If not, what are my options?

Key question

What does dp[i][j] mean, and what are the empty-string base cases?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Strings translate into production architectures and low-level memory mechanics.

LLD Architecture