Skip to main content
Talentd

Delete Operation for Two Strings - Solution & Explanation

MediumStringDynamic Programming18 min readAsked at: Amazon, Microsoft, Infosys +1
Practice this problem

Problem Statement

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.

 

Example 1:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Example 2:

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

 

Constraints:

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

Approach Overview

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.

Approach 1: Dynamic Programming with Longest Common Subsequence

This approach is based on finding the Longest Common Subsequence (LCS) between the two given strings. Once we have the LCS, the number of deletions needed is the sum of the lengths of the two strings minus twice the length of the LCS. The LCS represents the longest sequence that both strings have in common without rearranging their order. The deletions from either string will only be those characters not present in the LCS.

Here's a step-by-step process to solve the problem:

  1. Initialize a 2D array dp where dp[i][j] represents the length of LCS of string word1[0...i] and word2[0...j].
  2. Build up the dp array using the recurrence: if word1[i-1] == word2[j-1], then dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
  3. The result is len(word1) + len(word2) - 2 * dp[len(word1)][len(word2)].

This implementation computes the length of the Longest Common Subsequence (LCS) by filling up a 2D DP table. The result is derived by subtracting twice the LCS from the total length of the two input strings combined. The table is scanned row by row and filled based on the character match or recursive max value.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n), where m and n are the lengths of the two strings.
Space Complexity: O(m * n), as a 2D table is used for storing intermediate results.

Try this approach in the editor →

Approach 2: Dynamic Programming

We define f[i][j] as the minimum number of deletions required to make the first i characters of the string word1 and the first j characters of the string word2 the same. The answer is f[m][n], where m and n are the lengths of the strings word1 and word2, respectively.

Initially, if j = 0, then f[i][0] = i; if i = 0, then f[0][j] = j.

When i, j > 0, if word1[i - 1] = word2[j - 1], then f[i][j] = f[i - 1][j - 1]; otherwise, f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1.

Finally, return f[m][n].

The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the lengths of the strings word1 and word2, respectively.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Longest Common Subsequence

Time Complexity: O(m * n), where m and n are the lengths of the two strings.
Space Complexity: O(m * n), as a 2D table is used for storing intermediate results.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force RecursionO(2^(m+n))O(m+n)Conceptual understanding of the decision tree before optimization
Dynamic Programming with LCSO(m*n)O(m*n)General optimal solution for interview and production use
Space Optimized LCS DPO(m*n)O(min(m,n))When memory usage matters for very long strings

Video Solution

Delete Operation for Two Strings | Live Coding with Explanation | Leetcode - 583 • Algorithms Made Easy • 7,589 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Delete Operation for Two Strings easy or hard?
Delete Operation for Two Strings is rated Medium difficulty. The challenge lies in recognizing that the minimum deletions problem reduces to the Longest Common Subsequence dynamic programming pattern.
Delete Operation for Two Strings Python/Java solution
Python and Java implementations typically compute the LCS using a 2D DP array of size (m+1) x (n+1). After computing the LCS length, return (m - lcs) + (n - lcs). The same logic works in C++, JavaScript, and other languages.
How to solve Delete Operation for Two Strings in O(n)?
Strict O(n) time is not possible for the general case because every character pair may need comparison. The optimal solution runs in O(m*n) using Longest Common Subsequence dynamic programming. Space can be reduced to O(min(m,n)) by storing only two DP rows.
What is the best approach for Delete Operation for Two Strings?
The optimal approach uses Dynamic Programming with Longest Common Subsequence (LCS). First compute the LCS length of the two strings in O(m*n) time. The minimum deletions required equals (m - lcs) + (n - lcs), which removes all characters not part of the shared subsequence.
Is Delete Operation for Two Strings asked at Google/Amazon/Meta?
Dynamic programming problems based on Longest Common Subsequence frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving edit distance, deletions, or subsequence transformations are common technical interview questions.
What data structure is used in Delete Operation for Two Strings?
The core data structure is a 2D dynamic programming table. Each cell dp[i][j] stores the LCS length for prefixes of the two strings. The algorithm also relies on basic string traversal and index-based comparisons.
What is the time complexity of Delete Operation for Two Strings?
The optimal Dynamic Programming solution runs in O(m*n) time, where m and n are the lengths of the two strings. This comes from filling an LCS DP table that compares each character pair once. Space complexity is O(m*n) or O(min(m,n)) with optimization.

Ready to solve this problem?

Practice Delete Operation for Two Strings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Edit Distance

Next

Longest Common Subsequence