Loading problem...
You are given two strings, word1 and word2, each composed of lowercase English letters. Your task is to determine the minimum number of character removals required to make both strings identical.
In each operation, you may remove exactly one character from either string. The goal is to find the fewest total operations needed so that the remaining characters in both strings form the exact same sequence.
Key Insight: This problem is fundamentally connected to finding the Longest Common Subsequence (LCS) between the two strings. The characters that remain after optimal deletions form the LCS of the original strings. Therefore, the minimum number of deletions equals:
(length of word1) + (length of word2) - 2 × (length of LCS)
This is because we keep the LCS characters in both strings and delete everything else from each string.
word1 = "sea"
word2 = "eat"2The longest common subsequence is "ea" (length 2). To make both strings equal to "ea", we remove 's' from "sea" (1 deletion) and 't' from "eat" (1 deletion). Total deletions: 2.
word1 = "leetcode"
word2 = "etco"4The longest common subsequence is "etco" (length 4). The string "word2" is already "etco", so 0 deletions needed there. From "leetcode", we need to remove 'l', 'e', 'd', 'e' (4 deletions) to get "etco". Total deletions: 4.
word1 = "abc"
word2 = "abc"0Both strings are already identical. No deletions are needed.
Constraints