422. Delete Operation for Two Strings
You have two strings word1 and word2 made of lowercase English letters. Each step removes a single character of your choosing from whichever of the two strings you like — deletions are the only move; you can't insert or replace anything.
Compute and return the minimum number of steps required to make the two strings equal. Deleting everything is allowed, so two strings with no letters in common can always be reduced to a pair of empty strings.
Example 1:
Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: Delete the 's' from "sea" and the 't' from "eat": both become "ea" in 2 steps, and no single deletion can equalize them.
Example 2:
Input: word1 = "leetcode", word2 = "etco"
Output: 4
Explanation: The longest string both can shrink to is "etco" (a subsequence of both). "leetcode" must drop 4 letters to reach it, "etco" drops 0 — 4 steps total.
Constraints:
- 1 ≤ word1.length, word2.length ≤ 500
- word1 and word2 consist of lowercase English letters only
Hints:
Whatever survives the deletions is a string that appears in both words with its letters in order — a common subsequence. Making it as long as possible minimizes the deletions.
If the longest common subsequence has length L, the answer is |word1| + |word2| − 2·L. So this is the classic LCS table in disguise.
You can also fill a table for the answer directly: dp[i][j] = min deletions to equalize the first i letters of word1 and the first j of word2. Matching last letters cost nothing; otherwise delete from one word or the other.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: word1 = "sea", word2 = "eat"
Expected output: 2