Skip to main content

583. Delete Operation for Two Strings

medium

Find the minimum number of deletions to make two strings equal. Reduces cleanly to Longest Common Subsequence — answer is m + n - 2 * LCS.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same. In one step, you can delete exactly one character in either string.

Constraints

  • 1 <= word1.length, word2.length <= 500
  • word1 and word2 consist of only lowercase English letters.

Examples

Example 1

Input
word1 = "sea", word2 = "eat"
Output
2

Explanation: Delete 's' from sea and 't' from eat — both become 'ea'.

Example 2

Input
word1 = "leetcode", word2 = "etco"
Output
4

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Characters in the LCS are the ones you don't delete from either string.

Hint 2

Compute LCS length L. Answer = (m - L) + (n - L) = m + n - 2L.

Hint 3

Or solve directly: dp[i][j] = min deletions to make word1[0..i-1] and word2[0..j-1] equal.

Solution approach

Reveal approach

Reduce to Longest Common Subsequence. The characters preserved must form a common subsequence; to minimize deletions, preserve the longest one. Define subproblem dp[i][j] = LCS length of word1[0..i-1] and word2[0..j-1]. The recurrence relation is dp[i][j] = dp[i-1][j-1] + 1 if word1[i-1] == word2[j-1], otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Base cases dp[0][j] = dp[i][0] = 0. The answer is m + n - 2 * dp[m][n]. Alternative direct framing: dp[i][j] = min deletions to align word1[0..i-1] with word2[0..j-1], with dp[i][0] = i, dp[0][j] = j, and the same case split — but the LCS route is cleaner and reuses a well-known table. O(m * n) time and space; rolling rows give O(min(m, n)) space.

Complexity

Time
O(m * n)
Space
O(m * n)

Related patterns

  • dynamic-programming
  • memoization-recursion
  • string-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft

More Dynamic Programming practice problems

See all Dynamic Programming problems →