Problem Breakdown
We are given two strings, s1 and s2. Our objective is to transform both strings into a common subsequence by deleting characters from them. The cost of this transformation is defined as the sum of ASCII values of all deleted characters. We need to minimize this total cost.
- Inputs: Two strings
s1,s2containing lowercase English letters (ASCII 97-122). - Output: An integer representing the minimum possible deletion sum.
- Constraints: String lengths are between 0 and 1000. Since characters are standard ASCII, overflow is not a concern for standard integers ( fits easily in a 32-bit int).
Tricky Edge Cases:
- Empty strings: If one string is empty initially, we must delete all characters from the other. The DP base cases handle this naturally.
- No common subsequence possible (e.g., “abc”, “def”): We end up deleting everything from both strings.
- Identical strings: Cost should be 0.
Intuition
A brute-force approach would involve trying every combination of deletions to find the longest matching sequence, but that is exponential in complexity ( roughly), which will time out for .
This problem shares structural similarities with Longest Common Subsequence (LCS). In standard LCS, we maximize length. Here, we want to minimize deletion cost.
- If characters match (
s1[i] == s2[j]), it is optimal to keep them in the common subsequence because deleting either would incur a positive ASCII cost without benefit. The state transitions fromdp[i-1][j-1]. - If they don’t match, we have two choices: delete character from
s1or delete character froms2. We take the minimum of these paths plus their respective costs.
This suggests a Dynamic Programming approach where dp[i][j] stores the min cost to make prefixes s1[0..i-1] and s2[0..j-1] equal.
Approach
We will use an iterative bottom-up DP table of size (len(s1) + 1) x (len(s2) + 1).
-
Initialization: Create a 2D array initialized to infinity or handle base cases where one string is empty.
dp[0][j]represents the cost whens1is effectively empty, meaning we must delete all characters ofs2[:j]. This equals sum of ASCII values for that prefix.- Similarly,
dp[i][0]handles deleting all chars froms1.
-
Iteration: Loop through each character index
i(fors1) andj(fors2). -
Transition Logic:
- If
s1[i-1] == s2[j-1]: No deletion needed for this pair. Cost is same as previous diagonal:dp[i][j] = dp[i-1][j-1]. - Else (mismatch): We must delete one character from either string to proceed towards a match or empty state.
- Option 1: Delete char from
s1: Cost isdp[i-1][j] + ord(s1[i]) - Option 2: Delete char from
s2: Cost isdp[i][j-1] + ord(s2[j]) - Take the minimum of these two.
- Option 1: Delete char from
- If
-
Result: The value at
dp[len(s1)][len(s2)].
Complexity Analysis
- Time Complexity: , where and are lengths of
s1ands2. We visit each cell in the DP table once. With max length 1000, operations , well within time limits for Python (typically allowing ~1-5 seconds). - Space Complexity: to store the full DP table. This can be optimized to by only keeping two rows at a time if memory is tight, but given constraints (, for int array), standard space usage is acceptable and clearer for explanation.
Solution
class Solution:
def minimumDeleteSum(self, s1: str, s2: str) -> int:
m, n = len(s1), len(s2)
# dp[i][j] stores the min ASCII delete sum to make
# s1[:i] and s2[:j] equal.
# Dimensions are (m+1) x (n+1).
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Initialize first row: deleting all chars from s2 to match empty s1
current_sum_s2 = sum(ord(c) for c in s2)
# We can initialize the whole column/row logic inside loop or pre-fill.
# Pre-filling is cleaner but let's do it via loops for clarity of recurrence.
# Actually, simpler to fill base cases first:
dp[0][j] = current_sum_s2 # Wait, this needs prefix sum
# Let's refine initialization logic inside the loop or pre-calc row/col sums?
# Standard way: Initialize col 0 and row 0 with cumulative ASCII sums.
for i in range(m + 1):
dp[i][0] = sum(ord(c) for c in s1[:i]) if i > 0 else 0
current_sum_s2_prefix = [] # Not needed, just iterate
# Re-calculate row 0 properly: cost to delete all of s2[0..j-1]
dp[0][0] = 0
for j in range(1, n + 1):
dp[0][j] = dp[0][j - 1] + ord(s2[j - 1])
# Re-calculate col 0 properly: cost to delete all of s1[0..i-1]
for i in range(1, m + 1):
dp[i][0] = dp[i - 1][0] + ord(s1[i - 1])
# Fill the rest of the table
for i in range(1, m + 1):
char_s1 = s1[i - 1]
cost_char_s1 = ord(char_s1)
for j in range(1, n + 1):
char_s2 = s2[j - 1]
if char_s1 == char_s2:
# Characters match, no deletion needed for this pair.
# Cost is inherited from the diagonal state (both prefixes reduced by one).
dp[i][j] = dp[i - 1][j - 1]
else:
# Mismatch: choose min cost between deleting s1's char or s2's char
delete_from_s1 = dp[i - 1][j] + cost_char_s1
delete_from_s2 = dp[i][j - 1] + ord(char_s2)
dp[i][j] = min(delete_from_s1, delete_from_s2)
return dp[m][n]
Edge Cases Handled
- Empty Strings: The initialization loops handle
i=0andj=0. If input is empty strings or one string becomes effectively “deleted” (empty), the cumulative sum logic correctly returns 0 cost for matching empties. - No Common Characters: Logic naturally accumulates full ASCII sums of both strings in diagonal/edge cases if no matches occur, resulting in deleting everything from both.
- Identical Strings: The
if char_s1 == char_s2branch ensures we propagate 0 cost along the main diagonal for matching characters without adding deletion costs.