712. Minimum ASCII Delete Sum for Two Strings

How to solve Minimum ASCII Delete Sum for Two Strings (LeetCode 712): the approach in brief

The problem

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

Pattern

Minimum ASCII Delete Sum for Two Strings is a Dynamic Programming (DP) Patterns problem, in the 2D Array (Edit Distance / Levenshtein Distance) subpattern. The pattern covers fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break

Calculate minimum edit operations to transform one string to another using 2D DP.

Approach outline

1. Consider using dynamic programming to efficiently explore all possible ways to delete characters from both strings.
2. Think about defining a 2D DP array where each cell represents the minimum ASCII delete sum needed to make substrings of s1 and s2 equal.
3. Focus on how to relate the current state to previous states by comparing characters at the current indices of both strings.

Complexity

The reference solution runs in O(m * n) time and O(n) space.

Asked at

Minimum ASCII Delete Sum for Two Strings has been reported in interviews at TripleByte.