DSA Tracker

Visualize

Delete Operation for Two Strings

answer = len(word1) + len(word2) - 2 * LCS(word1, word2)

time O(m * n)space O(m * n)

No character in word1 needs to move or change — it only ever gets deleted or left alone, and word2 only ever gets characters inserted. So find the longest run of characters both strings already share IN ORDER (the LCS): those stay untouched. Everything else in word1 is deleted, and everything else in word2 is inserted. That gives (len(word1) - lcs) deletions plus (len(word2) - lcs) insertions.

Details

Animated on: word1 = "sea", word2 = "eat" — find the minimum insertions and deletions to make word1 equal word2.

Problem:Delete Operation for Two StringsMedium

answer = len(word1) + len(word2) - 2 * LCS(word1, word2)

step 1 / 11

LCS(word1="sea", word2="eat") — dp[i][j] = length of the LCS of the first i and j characters

Base case: an empty prefix shares 0 characters with anything, so the whole top row and left column start at 0.

Pseudocode
1FUNCTION minInsDel(word1, word2):
2  m <- LENGTH(word1)
3  n <- LENGTH(word2)
4  FOR i FROM 0 TO m: dp[i][0] <- 0
5  FOR j FROM 0 TO n: dp[0][j] <- 0
6  FOR i FROM 1 TO m:
7    FOR j FROM 1 TO n:
8      IF word1[i-1] = word2[j-1]:
9        dp[i][j] <- dp[i-1][j-1] + 1
10      ELSE:
11        dp[i][j] <- MAX(dp[i-1][j], dp[i][j-1])
12  lcs <- dp[m][n]
13  RETURN m + n - 2 * lcs

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. Base case: an empty prefix shares 0 characters with anything, so the whole top row and left column start at 0.
  2. word1[0]='s' != word2[0]='e': no new match, so carry the better of dropping one side, dp[1][1] = MAX(dp[0][1]=0, dp[1][0]=0) = 0.
  3. word1[0]='s' != word2[1]='a': no new match, so carry the better of dropping one side, dp[1][2] = MAX(dp[0][2]=0, dp[1][1]=0) = 0.
  4. word1[0]='s' != word2[2]='t': no new match, so carry the better of dropping one side, dp[1][3] = MAX(dp[0][3]=0, dp[1][2]=0) = 0.
  5. word1[1]='e' matches word2[0]='e': extend the diagonal, dp[2][1] = dp[1][0] + 1 = 1.
  6. word1[1]='e' != word2[1]='a': no new match, so carry the better of dropping one side, dp[2][2] = MAX(dp[1][2]=0, dp[2][1]=1) = 1.
  7. word1[1]='e' != word2[2]='t': no new match, so carry the better of dropping one side, dp[2][3] = MAX(dp[1][3]=0, dp[2][2]=1) = 1.
  8. word1[2]='a' != word2[0]='e': no new match, so carry the better of dropping one side, dp[3][1] = MAX(dp[2][1]=1, dp[3][0]=0) = 1.
  9. word1[2]='a' matches word2[1]='a': extend the diagonal, dp[3][2] = dp[2][1] + 1 = 2.
  10. word1[2]='a' != word2[2]='t': no new match, so carry the better of dropping one side, dp[3][3] = MAX(dp[2][3]=1, dp[3][2]=2) = 2.
  11. dp[3][3] = 2: the LCS of "sea" and "eat" has length 2. Delete the 1 leftover character from word1 and insert the 1 leftover character from word2: 1 + 1 = 2 operations.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Delete Operation for Two Strings in the editorAll Dynamic Programming problemsBack to roadmap