Delete Operation for Two Strings - Solution & Explanation

Problem Overview: Given two strings word1 and word2, return the minimum number of delete operations required to make both strings identical. You can delete characters from either string, but you cannot insert or replace.

Approach 1: Brute Force Recursion (Exponential Time)

Try every possible deletion choice recursively. If the current characters match, move both pointers forward. If they differ, branch into two possibilities: delete from word1 or delete from word2. Take the minimum result from both paths. This explores a full decision tree with repeated subproblems, leading to O(2^(m+n)) time and O(m+n) recursion stack space. Useful for understanding the state transition before introducing memoization or dynamic programming.

Approach 2: Dynamic Programming with Longest Common Subsequence (O(m*n))

The key insight: both strings become equal when only their Longest Common Subsequence (LCS) remains. Any character not part of the LCS must be deleted. If the LCS length is lcs, then the required deletions equal (m - lcs) + (n - lcs), where m and n are the lengths of the two strings.

Compute the LCS using classic Dynamic Programming. Build a (m+1) x (n+1) DP table where dp[i][j] stores the LCS length of the first i characters of word1 and first j characters of word2. If characters match, extend the subsequence using dp[i-1][j-1] + 1. Otherwise take max(dp[i-1][j], dp[i][j-1]). This runs in O(m*n) time with O(m*n) space.

The approach works because deleting characters until both strings equal the LCS ensures the minimum number of operations. The DP transition mirrors the classic String comparison pattern used in the Dynamic Programming formulation of Longest Common Subsequence.

Recommended for interviews: Dynamic Programming using the Longest Common Subsequence. Interviewers expect candidates to recognize that the minimum deletions problem reduces directly to LCS. Starting with the brute-force recursion shows you understand the decision process, but deriving the LCS relationship and implementing the O(m*n) DP demonstrates strong algorithmic thinking.