DP on Strings | Minimum ASCII Delete Sum for Two Strings | LeetCode 712

In this video, we solve LeetCode 712. Minimum ASCII Delete Sum for Two Strings using a clean Dynamic Programming approach.

The key idea is to think in terms of cost, not just matching characters:
If characters match, we keep them with zero cost
If they don’t, we delete one character and pay its ASCII value

Instead of directly finding the common string, we compute the minimum total ASCII cost required to make both strings equal.

We define a DP state where:

dp[i][j] represents the minimum delete cost to make
s1[0..i] and s2[0..j] equal
Base cases handle deleting all remaining characters from one string and we use prefix sums to handle this efficiently
Transitions choose the cheaper deletion when characters differ
This leads to an optimal O(n × m) solution.

This problem is part of today’s LeetCode Daily Problem of the Day (POTD).

🔹 What you’ll learn:
• How to model string problems as cost minimization
• Why ASCII values naturally define deletion cost
• How base cases simplify edge conditions
• Top-down DP with memoization

🔹 Topics:
• Dynamic Programming
• String DP
• Memoization
• Prefix Sums

Clear problem explanation, intuition-first walkthrough, and clean Java implementation.

Problem link - https://leetcode.com/problems/minimum...

Java Code - https://pastebin.com/QG6zFLTH
Python Code - https://pastebin.com/6rfa1fen

Time complexity - O(N*M)
Space Complexity - O(N*M)

Page Marker Extension - https://chromewebstore.google.com/det...

Video Chapters -
00:00 - Problem Statement
02:35 - Approach
12:29 - Code
24:27 - Time and Space Complexity


Leetcode daily playlist -    • LeetCode Daily Problems  

LeetCode Easy POTD playlist -    • LeetCode Easy  

LeetCode Medium POTD playlist -    • LeetCode Medium  

LeetCode Hard POTD playlist -    • LeetCode Hard  

If you want to practice daily and improve your problem-solving skills, this is the place to follow along.

#leetcode #dsa #dp #memoization #prefixsum #strings #dynamicprogramming #leetcodeproblemoftheday #algorithm #java #python #code #leetcodechallenge #codinginterview #problemsolving