Delete Operation for Two Strings

Delete Operation for Two Strings is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Longest Common Subsequence - LCS) subpattern.

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.

Topics and companies

Topics: String, Dynamic Programming.

Reported in interviews at Google.

How to practise Delete Operation for Two Strings on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(n) space.

Open Delete Operation for Two Strings in the code editor, or read the Delete Operation for Two Strings editorial for a worked solution with its approach and complexity analysis.

Where Delete Operation for Two Strings sits in the DSA pattern sheet

• Dynamic Programming (DP) Patterns pattern guide
• 2D Array (Longest Common Subsequence - LCS) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Delete Operation for Two Strings

Other problems that use the same 2D Array (Longest Common Subsequence - LCS) and Dynamic Programming (DP) Patterns techniques:

• Edit Distance — Medium, same subpattern
• Minimum ASCII Delete Sum for Two Strings — Medium, same subpattern
• Best Time to Buy and Sell Stock — Easy, same pattern
• Best Time to Buy and Sell Stock II — Medium, same pattern
• Best Time to Buy and Sell Stock III — Hard, same pattern
• Best Time to Buy and Sell Stock IV — Hard, same pattern