#583

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Delete Operation for Two Strings

Find the minimum number of steps to make two strings equal by deleting characters, using dynamic programming.

Problem Statement

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

For example, given word1 = "sea" and word2 = "eat", you can remove the 's' from word1 and the 't' from word2, leaving 'ea' in both, requiring 2 deletions in total.

Examples

Example 1

Input: word1 = "sea", word2 = "eat"

Output: 2

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

Example details omitted.

Constraints

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

Solution Approach

Dynamic Programming Approach

We use a dynamic programming table to find the longest common subsequence (LCS) of the two strings. The minimum number of deletions is then the total length of both strings minus twice the length of the LCS.

State Transition

Each state in the DP table represents the solution for substrings of word1 and word2. If characters match, we extend the solution; otherwise, we choose the minimum cost by deleting from one of the strings.

Time and Space Complexity

The time complexity is O(m * n) where m and n are the lengths of the two strings. The space complexity is also O(m * n) for the DP table.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(m * n), where m and n are the lengths of the two input strings. The space complexity is also O(m * n) due to the storage needed for the dynamic programming table, which tracks the length of the longest common subsequence at each state of the solution.

What Interviewers Usually Probe

The candidate understands dynamic programming concepts like state transitions and recursive relations.
The candidate should explain how they arrived at the minimum deletions by subtracting the LCS length from the total string lengths.
The candidate can efficiently describe time and space complexity in terms of the problem's constraints.

Common Pitfalls or Variants

Common pitfalls

Confusing the problem with a subsequence matching problem without considering deletions.
Overcomplicating the dynamic programming table and not explaining the base cases properly.
Not considering edge cases like empty strings or strings with no common characters.

Follow-up variants

Variant 1: Finding the minimum steps to make the strings equal by inserting characters.
Variant 2: Extending this problem to consider insertions and deletions to make two strings identical.
Variant 3: Modifying the problem to allow character replacements in addition to deletions.

FAQ

How do I approach the Delete Operation for Two Strings problem?

Use dynamic programming to compute the longest common subsequence (LCS), then subtract twice the LCS length from the total length of the strings to find the minimum deletions.

What is the time complexity of the Delete Operation for Two Strings problem?

The time complexity is O(m * n), where m and n are the lengths of the two strings.

What are the key steps in solving the Delete Operation for Two Strings problem?

First, compute the longest common subsequence (LCS) using dynamic programming. Then calculate the minimum deletions as the sum of the lengths of the two strings minus twice the LCS length.

What is the space complexity of this problem?

The space complexity is O(m * n) due to the DP table storing the LCS values.

Can I optimize space for the Delete Operation for Two Strings problem?

Yes, you can reduce the space complexity by storing only the current and previous rows of the DP table instead of the entire table.

terminal

Solution

Solution 1: Dynamic Programming

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            f[i][0] = i
        for j in range(1, n + 1):
            f[0][j] = j
        for i, a in enumerate(word1, 1):
            for j, b in enumerate(word2, 1):
                if a == b:
                    f[i][j] = f[i - 1][j - 1]
                else:
                    f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1
        return f[m][n]

Continue Practicing

#639 decode ways ii #647 palindromic substrings #516 longest palindromic subsequence