DSA
Delete Operation for Two Strings
4 approaches incl. Brute Force, Recursive, Memoized DP, and more. Optimal — Time O(m*n), Space O(n).
Practice Link
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.
Brute Force#
- Find all the subsequences of both strings and compare.
- The key insight is that the minimum deletions equals (m + n) - 2 * LCS(word1, word2): we keep the longest common subsequence intact and delete everything else from both strings.
O(2^(m + n)) -> TLE (Overlapping subproblems)
Recursive#
Reduce the problem to finding the Longest Common Subsequence (LCS). At each step, if the last characters match, they're part of the LCS and we recurse on (m-1, n-1); otherwise we try removing the last character of either string and take the best. The minimum deletions is then (m + n) - 2 * LCS. Without caching, the same (m, n) subproblems are recomputed exponentially.
class Solution {
public:
int lcs(string text1, string text2, int m, int n)
{
if(m==0 || n==0)
return 0;
if(text1[m-1] == text2[n-1])
return 1 + lcs(text1, text2, m-1, n-1);
return max(lcs(text1, text2, m-1, n), lcs(text1, text2, m, n-1));
}
int minDistance(string word1, string word2) {
int m = word1.length();
int n = word2.length();
int lcsLength = lcs(word1, word2, m, n);
return (m+n) - (2*lcsLength);
}
};
O(2^n) -> TLE (Overlapping subproblems)
Memoized DP Approach#
Cache LCS results in memo[m][n]. Each of the (m+1) × (n+1) unique states is computed exactly once, reducing time from exponential to O(m*n). The result formula (m + n) - 2 * LCS then converts the LCS length into the minimum deletion count.
class Solution {
public:
int lcs(string text1, string text2, int m, int n, vector<vector<int>> &memo)
{
if(m==0 || n==0)
return 0;
if(memo[m][n] != -1)
return memo[m][n];
if(text1[m-1] == text2[n-1])
memo[m][n] = 1 + lcs(text1, text2, m-1, n-1, memo);
else
memo[m][n] = max(lcs(text1, text2, m-1, n, memo), lcs(text1, text2, m, n-1, memo));
return memo[m][n];
}
int minDistance(string word1, string word2) {
int m = word1.length();
int n = word2.length();
vector<vector<int>> memo(m+1, vector<int>(n+1, -1));
int lcsLength = lcs(word1, word2, m, n, memo);
return (m+n) - (2*lcsLength);
}
};
Time Complexity: O(m*n)
Space Compelexity: O(m*n) + O(n) -> recursive stack
DP Approach#
Build the LCS bottom-up in a 2D table. dp[i][j] = length of LCS of word1[0..i-1] and word2[0..j-1]. Fill row by row: match extends the diagonal, mismatch takes the max of the left or top cell. This iterative fill eliminates recursive call-stack overhead while maintaining O(m*n) time and space.
class Solution {
public:
int lcs(string text1, string text2, int m, int n)
{
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(text1[i-1] == text2[j-1])
dp[i][j] = 1 + dp[i-1][j-1];
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}
int minDistance(string word1, string word2) {
int m = word1.length();
int n = word2.length();
int lcsLength = lcs(word1, word2, m, n);
return (m+n) - (2*lcsLength);
}
};
Time Complexity: O(m*n)
Space Compelexity: O(m*n)
Space Optimized Tabulation#
Each row of the LCS table only reads from the previous row. We keep two 1D arrays (prev and curr) of length n+1 and swap them after each character of word1. Space drops from O(mn) to O(n) with the same O(mn) time.
class Solution {
public:
int lcs(string text1, string text2, int m, int n)
{
vector<int> prev(n+1, 0);
vector<int> curr(n+1, 0);
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(text1[i-1] == text2[j-1])
curr[j] = 1 + prev[j-1];
else
curr[j] = max(prev[j], curr[j-1]);
}
prev = curr;
}
return prev[n];
}
int minDistance(string word1, string word2) {
int m = word1.length();
int n = word2.length();
int lcsLength = lcs(word1, word2, m, n);
return (m+n) - (2*lcsLength);
}
};
Time Complexity: O(m*n)
Space Compelexity: O(n)