Delete Operation for Two Strings - Practice Coding Problems

Delete Operation for Two Strings - 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.

The goal is to find the minimum number of deletions needed so that both strings become identical.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: Delete 's' from word1 and 't' from word2 to make both strings "ea". Total: 2 deletions.

Example 2 — No Common Characters

$ Input: word1 = "abc", word2 = "def"

› Output: 6

💡 Note: No common characters, so delete all 3 characters from word1 and all 3 from word2. Total: 6 deletions.

Example 3 — Identical Strings

$ Input: word1 = "hello", word2 = "hello"

› Output: 0

💡 Note: Strings are already identical, no deletions needed.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Strings

Two strings that need to become identical

Find Common Parts

Identify longest common subsequence to keep

Calculate Deletions

Delete all characters not in common subsequence

Key Takeaway

🎯 Key Insight: Find the longest common subsequence and delete everything else - this gives the minimum number of deletions needed.

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is to find the longest common subsequence (LCS) between both strings and delete everything else. The minimum deletions needed equals the total length of both strings minus twice the LCS length. Best approach uses 2D dynamic programming or LCS-based solution. Time: O(m×n), Space: O(min(m,n)) with optimization.

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Brute Force	O(2^(m+n))	O(m+n)	Try all possible deletion combinations recursively
Memoized Recursion	O(m×n)	O(m×n)	Cache recursive results to avoid recomputation
2D Dynamic Programming	O(m×n)	O(m×n)	Bottom-up DP table to find minimum deletions
LCS-Based Approach	O(m×n)	O(min(m,n))	Find longest common subsequence, then calculate deletions

Recursive Brute Force — Algorithm Steps

Compare characters at current positions
If match, move both pointers forward
If no match, try deleting from either string
Return minimum of all possibilities

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Characters

At each position, compare current characters

Branch Decisions

If different, try deleting from either string

Find Minimum

Return the path with minimum deletions

Code -

solution.c — C

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

int helper(char* word1, char* word2, int i, int j, int len1, int len2) {
    if (i == len1) {
        return len2 - j;
    }
    if (j == len2) {
        return len1 - i;
    }
    
    if (word1[i] == word2[j]) {
        return helper(word1, word2, i + 1, j + 1, len1, len2);
    } else {
        int delete1 = 1 + helper(word1, word2, i + 1, j, len1, len2);
        int delete2 = 1 + helper(word1, word2, i, j + 1, len1, len2);
        return delete1 < delete2 ? delete1 : delete2;
    }
}

int solution(char* word1, char* word2) {
    return helper(word1, word2, 0, 0, strlen(word1), strlen(word2));
}

int main() {
    char word1[1001], word2[1001];
    fgets(word1, sizeof(word1), stdin);
    fgets(word2, sizeof(word2), stdin);
    word1[strcspn(word1, "\n")] = 0;
    word2[strcspn(word2, "\n")] = 0;
    int result = solution(word1, word2);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^(m+n))

Each position has up to 3 recursive calls, creating exponential branches

✓ Linear Growth

Space Complexity

O(m+n)

Recursion depth can go up to sum of string lengths

⚡ Linearithmic Space

78.5K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler