583. Delete Operation for Two Strings - Solution

The 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.

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:

Initialize a 2D array dp where dp[i][j] represents the length of LCS of string word1[0...i] and word2[0...j].
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]).
The result is len(word1) + len(word2) - 2 * dp[len(word1)][len(word2)].

Python

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return m + n - 2 * dp[m][n]

# Example usage
word1 = "sea"
word2 = "eat"
print(minDistance(word1, word2))

Java

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return m + n - 2 * dp[m][n];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minDistance("sea", "eat"));
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

int minDistance(string word1, string word2) {
    int len1 = word1.length();
    int len2 = word2.length();
    vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (word1[i-1] == word2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return len1 + len2 - 2 * dp[len1][len2];
}

int main() {
    string word1 = "sea";
    string word2 = "eat";
    cout << minDistance(word1, word2) << endl;
    return 0;
}

JavaScript

function minDistance(word1, word2) {
    const m = word1.length;
    const n = word2.length;
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return m + n - 2 * dp[m][n];
}

// Example usage
const word1 = "sea";
const word2 = "eat";
console.log(minDistance(word1, word2));

#include <stdio.h>
#include <string.h>

int minDistance(char *word1, char *word2) {
    int len1 = strlen(word1);
    int len2 = strlen(word2);
    int dp[len1 + 1][len2 + 1];
    for (int i = 0; i <= len1; i++) dp[i][0] = 0;
    for (int j = 0; j <= len2; j++) dp[0][j] = 0;
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (word1[i - 1] == word2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
        }
    }
    return len1 + len2 - 2 * dp[len1][len2];
}

int main() {
    char word1[] = "sea";
    char word2[] = "eat";
    printf("%d\n", minDistance(word1, word2));
    return 0;
}

using System;

class Program {
    public static int MinDistance(string word1, string word2) {
        int m = word1.Length;
        int n = word2.Length;
        int[,] dp = new int[m + 1, n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i, j] = dp[i - 1, j - 1] + 1;
                } else {
                    dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
                }
            }
        }
        return m + n - 2 * dp[m, n];
    }

    static void Main() {
        string word1 = "sea";
        string word2 = "eat";
        Console.WriteLine(MinDistance(word1, word2));
    }
}

In Python, we utilize nested loops to fill up a two-dimensional list. The logic for updating the DP table elements involves checking character matches and updating based on prior results in the table, effectively calculating the LCS length before using it to determine the final answer in terms of deletions.

Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n) for the storage required for the DP matrix.

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.

TypeScript

function minDistance(word1: string, word2: string): number {
    const m = word1.length;
    const n = word2.length;
    const f: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    for (let i = 1; i <= m; ++i) {
        f[i][0] = i;
    }
    for (let j = 1; j <= n; ++j) {
        f[0][j] = j;
    }
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            if (word1[i - 1] === word2[j - 1]) {
                f[i][j] = f[i - 1][j - 1];
            } else {
                f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + 1;
            }
        }
    }
    return f[m][n];
}

func minDistance(word1 string, word2 string) int {
	m, n := len(word1), len(word2)
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
        f[i][0] = i
	}
	for j := 1; j <= n; j++ {
		f[0][j] = j
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			a, b := word1[i-1], word2[j-1]
			if a == b {
				f[i][j] = f[i-1][j-1]
			} else {
				f[i][j] = 1 + min(f[i-1][j], f[i][j-1])
			}
		}
	}
	return f[m][n]
}

Rust

impl Solution {
    pub fn min_distance(word1: String, word2: String) -> i32 {
        let m = word1.len();
        let n = word2.len();
        let s: Vec<char> = word1.chars().collect();
        let t: Vec<char> = word2.chars().collect();
        let mut f = vec![vec![0; n + 1]; m + 1];

        for i in 0..=m {
            f[i][0] = i as i32;
        }
        for j in 0..=n {
            f[0][j] = j as i32;
        }

        for i in 1..=m {
            for j in 1..=n {
                let a = s[i - 1];
                let b = t[j - 1];
                if a == b {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    f[i][j] = std::cmp::min(f[i - 1][j], f[i][j - 1]) + 1;
                }
            }
        }
        f[m][n]
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming with Longest Common Subsequence	Time Complexity: O(m * n) Space Complexity: O(m * n) for the storage required for the DP matrix.
Dynamic Programming	–

Complexity analysis

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

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.

Delete Operation for Two Strings solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Longest Common Subsequence

Approach 2: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Delete Operation for Two Strings solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Longest Common Subsequence

Approach 2: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems