Minimum ASCII Delete Sum for Two Strings - Practice Coding Problems

Minimum ASCII Delete Sum for Two Strings - Problem

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

When you delete a character from either string, you add its ASCII value to the total cost. Your goal is to find the minimum total cost needed to make both strings identical.

Note: The final equal strings can be any string that can be formed by deleting characters from both input strings.

Input & Output

Example 1 — Basic Case

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

› Output: 231

💡 Note: Delete 's' from "sea" (ASCII 115) and 't' from "eat" (ASCII 116). Both become "ea". Total cost: 115 + 116 = 231.

Example 2 — One String Empty

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

› Output: 631

💡 Note: Delete all characters from "delete": d(100) + e(101) + l(108) + e(101) + t(116) + e(101) = 631.

Example 3 — Identical Strings

$ Input: s1 = "abc", s2 = "abc"

› Output: 0

💡 Note: Strings are already identical, no deletions needed. Cost = 0.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Strings

s1="sea" and s2="eat" with different characters

Find Common Parts

Identify shared subsequence "ea" to keep

Calculate Deletions

Delete 's'(115) + 't'(116) = 231 total cost

Key Takeaway

🎯 Key Insight: Keep the longest common subsequence, delete everything else with minimum ASCII cost

Asked in

G Google 15 M Microsoft 12 a Amazon 8 f Facebook 6

The key insight is to find the longest common subsequence and delete everything else. This is similar to edit distance but with ASCII deletion costs instead of unit costs. Best approach is 2D Dynamic Programming building solutions bottom-up. Time: O(m×n), Space: O(m×n).

Common Approaches

Approach	Time	Space	Notes
✓ 2D Dynamic Programming	O(m×n)	O(m×n)	Build solution bottom-up using a 2D table
Brute Force Recursion	O(2^(m+n))	O(m+n)	Recursively try all possible deletions and pick minimum cost
Memoization (Top-Down DP)	O(m×n)	O(m×n)	Cache recursive results to avoid recomputing same subproblems

2D Dynamic Programming — Algorithm Steps

Initialize DP table with base cases
Fill table row by row
For each cell, choose minimum of three options
Return dp[m][n] as final answer

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Base Cases

Fill first row and column with deletion costs

Fill Table

For each cell, choose minimum deletion cost

Final Answer

Bottom-right cell contains minimum cost

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int solution(const char* s1, const char* s2) {
    int m = strlen(s1), n = strlen(s2);
    // dp[i][j] = min cost to make s1[0:i] and s2[0:j] equal
    int** dp = (int**)malloc((m + 1) * sizeof(int*));
    for (int i = 0; i <= m; i++) {
        dp[i] = (int*)calloc(n + 1, sizeof(int));
    }
    
    // Base cases: delete all characters from one string
    for (int i = 1; i <= m; i++) {
        dp[i][0] = dp[i-1][0] + (int) s1[i-1];
    }
    
    for (int j = 1; j <= n; j++) {
        dp[0][j] = dp[0][j-1] + (int) s2[j-1];
    }
    
    // Fill DP table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                // Characters match, no deletion needed
                dp[i][j] = dp[i-1][j-1];
            } else {
                // Choose minimum: delete from s1 or s2
                int deleteS1 = dp[i-1][j] + (int) s1[i-1];
                int deleteS2 = dp[i][j-1] + (int) s2[j-1];
                dp[i][j] = deleteS1 < deleteS2 ? deleteS1 : deleteS2;
            }
        }
    }
    
    int result = dp[m][n];
    
    // Free memory
    for (int i = 0; i <= m; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

int main() {
    char s1[1001], s2[1001];
    fgets(s1, sizeof(s1), stdin);
    s1[strcspn(s1, "\n")] = 0;
    fgets(s2, sizeof(s2), stdin);
    s2[strcspn(s2, "\n")] = 0;
    
    int result = solution(s1, s2);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Double nested loop fills m×n table entries

✓ Linear Growth

Space Complexity

O(m×n)

2D DP table stores results for all string prefix combinations

⚡ Linearithmic Space

89.5K Views

Medium Frequency

~25 min Avg. Time

2.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

2D Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler