Delete Operation for Two Strings

🎯

Delete Operation for Two Strings

mediumDPAmazonGoogle

Imagine you have two versions of a document and want to make them identical by deleting characters only. How many deletions are needed?

💡 This problem is a classic dynamic programming challenge involving strings. Beginners often struggle because it requires understanding how to break down the problem into subproblems and how to use the Longest Common Subsequence (LCS) concept to minimize deletions.

📋

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.

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

💡

Example

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

Output2

Delete 's' from "sea" and 't' from "eat" to make both strings "ea".

Input"word1 = \"leetcode\", word2 = \"etco\""

Output4

Delete 'l', 'd', 'e', 'e' from "leetcode" to get "etco".

• One or both strings empty → output is length of the other string
• Both strings identical → output is 0
• Strings with no common characters → output is sum of lengths
• Strings with repeated characters → ensure correct counting

🔁

Why DP?

Why greedy fails:

A greedy approach might try to delete characters from one string to match the other immediately, but this fails when characters appear out of order. For example, word1 = 'abc', word2 = 'cba'. Greedy deletion from front or back won't find the minimal deletions.

DP state:

dp[i][j] represents the minimum number of deletions required to make the substrings word1[i:] and word2[j:] identical.

Recurrence:dp[i][j] = if word1[i] == word2[j] then dp[i+1][j+1] else 1 + min(dp[i+1][j], dp[i][j+1])

If characters match, no deletion needed here; move both pointers. Otherwise, delete one character from either string and add 1 to the count.

⚠️

Common Mistakes

Not handling base cases correctly

Incorrect results or index errors

✅ Explicitly initialize dp for empty suffixes

Mixing up indices i and j in recursion or DP

Wrong subproblems computed, wrong answer

✅ Carefully track which index corresponds to which string

Not memoizing recursive calls

TLE due to exponential time

✅ Use a cache keyed by (i,j) to store results

Incorrect iteration order in bottom-up DP

Using uninitialized dp values leads to wrong answers

✅ Fill dp from bottom-right to top-left

In space optimized DP, iterating forwards instead of backwards

Overwrites needed dp values, causing incorrect results

✅ Iterate j from n-1 down to 0

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive structure and why naive solutions are inefficient due to repeated computations.

Intuition

Try all possible deletions by recursively deleting characters from either string until both become equal.

Algorithm

1. If either string is empty, return the length of the other (all deletions).
2. If first characters match, recurse on the remaining substrings.
3. Otherwise, try deleting from word1 or word2 and take the minimum.
4. Return the minimum deletions found.

💡 The recursion explores all deletion choices, which is conceptually simple but inefficient.

Recurrence:dp(i,j) = if word1[i] == word2[j] then dp(i+1,j+1) else 1 + min(dp(i+1,j), dp(i,j+1))

</>

Code

def minDistance(word1, word2):
    def dfs(i, j):
        if i == len(word1):
            return len(word2) - j
        if j == len(word2):
            return len(word1) - i
        if word1[i] == word2[j]:
            return dfs(i+1, j+1)
        else:
            return 1 + min(dfs(i+1, j), dfs(i, j+1))
    return dfs(0, 0)

# Example usage
if __name__ == '__main__':
    print(minDistance('sea', 'eat'))  # Output: 2

Line Notes

def dfs(i, j):Defines recursive helper to compute deletions from indices i and j

if i == len(word1):If word1 exhausted, delete all remaining chars in word2

if j == len(word2):If word2 exhausted, delete all remaining chars in word1

if word1[i] == word2[j]:If chars match, no deletion needed, move both pointers

return 1 + min(dfs(i+1, j), dfs(i, j+1))Delete one char from either string and recurse

public class Solution {
    public int minDistance(String word1, String word2) {
        return dfs(word1, word2, 0, 0);
    }
    private int dfs(String w1, String w2, int i, int j) {
        if (i == w1.length()) return w2.length() - j;
        if (j == w2.length()) return w1.length() - i;
        if (w1.charAt(i) == w2.charAt(j)) {
            return dfs(w1, w2, i + 1, j + 1);
        } else {
            return 1 + Math.min(dfs(w1, w2, i + 1, j), dfs(w1, w2, i, j + 1));
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minDistance("sea", "eat")); // 2
    }
}

Line Notes

public int minDistance(String word1, String word2)Entry point calling recursive helper

if (i == w1.length())If word1 exhausted, delete remaining word2 chars

if (j == w2.length())If word2 exhausted, delete remaining word1 chars

if (w1.charAt(i) == w2.charAt(j))If chars match, move both pointers

return 1 + Math.min(...)Delete one char from either string and recurse

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

class Solution {
public:
    int dfs(const string& w1, const string& w2, int i, int j) {
        if (i == w1.size()) return w2.size() - j;
        if (j == w2.size()) return w1.size() - i;
        if (w1[i] == w2[j]) return dfs(w1, w2, i + 1, j + 1);
        return 1 + min(dfs(w1, w2, i + 1, j), dfs(w1, w2, i, j + 1));
    }
    int minDistance(string word1, string word2) {
        return dfs(word1, word2, 0, 0);
    }
};

int main() {
    Solution sol;
    cout << sol.minDistance("sea", "eat") << endl; // 2
    return 0;
}

Line Notes

int dfs(const string& w1, const string& w2, int i, int j)Recursive helper with indices i, j

if (i == w1.size())If word1 exhausted, delete remaining word2 chars

if (j == w2.size())If word2 exhausted, delete remaining word1 chars

if (w1[i] == w2[j])If chars match, move both pointers

return 1 + min(...)Delete one char from either string and recurse

function minDistance(word1, word2) {
    function dfs(i, j) {
        if (i === word1.length) return word2.length - j;
        if (j === word2.length) return word1.length - i;
        if (word1[i] === word2[j]) return dfs(i + 1, j + 1);
        return 1 + Math.min(dfs(i + 1, j), dfs(i, j + 1));
    }
    return dfs(0, 0);
}

// Example usage
console.log(minDistance('sea', 'eat')); // 2

Line Notes

function dfs(i, j)Recursive helper function with indices i and j

if (i === word1.length)If word1 exhausted, delete remaining word2 chars

if (j === word2.length)If word2 exhausted, delete remaining word1 chars

if (word1[i] === word2[j])If chars match, move both pointers

return 1 + Math.min(...)Delete one char from either string and recurse

⏱

Complexity

TimeO(2^(m+n))

SpaceO(m+n) due to recursion stack

Each call branches into two when characters differ, leading to exponential calls.

💡 For strings of length 10, this could mean over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's recursive nature.

🧠

Top-Down DP with Memoization

💡 Memoization avoids recomputing the same subproblems, drastically improving efficiency while keeping the recursive structure.

Intuition

Store results of recursive calls in a cache so repeated calls return instantly.

Algorithm

1. Initialize a memo dictionary to store results for (i, j).
2. If (i, j) in memo, return stored result.
3. If characters match, recurse on next indices.
4. Otherwise, compute 1 + min of deleting from either string.
5. Store and return the result.

💡 Memoization prunes the recursion tree by caching results, preventing exponential blowup.

Recurrence:dp(i,j) = if word1[i] == word2[j] then dp(i+1,j+1) else 1 + min(dp(i+1,j), dp(i,j+1))

</>

Code

def minDistance(word1, word2):
    memo = {}
    def dfs(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        if i == len(word1):
            memo[(i, j)] = len(word2) - j
            return memo[(i, j)]
        if j == len(word2):
            memo[(i, j)] = len(word1) - i
            return memo[(i, j)]
        if word1[i] == word2[j]:
            memo[(i, j)] = dfs(i+1, j+1)
        else:
            memo[(i, j)] = 1 + min(dfs(i+1, j), dfs(i, j+1))
        return memo[(i, j)]
    return dfs(0, 0)

# Example usage
if __name__ == '__main__':
    print(minDistance('sea', 'eat'))  # Output: 2

Line Notes

memo = {}Cache to store results of subproblems

if (i, j) in memo:Return cached result if available

memo[(i, j)] = len(word2) - jBase case: delete all remaining chars in word2

memo[(i, j)] = len(word1) - iBase case: delete all remaining chars in word1

memo[(i, j)] = dfs(i+1, j+1)If chars match, recurse without deletion

memo[(i, j)] = 1 + min(...)If chars differ, delete one char and recurse

import java.util.*;
public class Solution {
    private Map<String, Integer> memo = new HashMap<>();
    public int minDistance(String word1, String word2) {
        return dfs(word1, word2, 0, 0);
    }
    private int dfs(String w1, String w2, int i, int j) {
        String key = i + "," + j;
        if (memo.containsKey(key)) return memo.get(key);
        if (i == w1.length()) {
            memo.put(key, w2.length() - j);
            return memo.get(key);
        }
        if (j == w2.length()) {
            memo.put(key, w1.length() - i);
            return memo.get(key);
        }
        int res;
        if (w1.charAt(i) == w2.charAt(j)) {
            res = dfs(w1, w2, i + 1, j + 1);
        } else {
            res = 1 + Math.min(dfs(w1, w2, i + 1, j), dfs(w1, w2, i, j + 1));
        }
        memo.put(key, res);
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minDistance("sea", "eat")); // 2
    }
}

Line Notes

private Map<String, Integer> memo = new HashMap<>();Cache to store computed results

String key = i + "," + j;Unique key for memoization based on indices

if (memo.containsKey(key))Return cached result if present

memo.put(key, w2.length() - j);Base case: delete remaining chars in word2

memo.put(key, w1.length() - i);Base case: delete remaining chars in word1

memo.put(key, res);Store computed result before returning

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
    unordered_map<string, int> memo;
    int dfs(const string& w1, const string& w2, int i, int j) {
        string key = to_string(i) + "," + to_string(j);
        if (memo.count(key)) return memo[key];
        if (i == w1.size()) return memo[key] = w2.size() - j;
        if (j == w2.size()) return memo[key] = w1.size() - i;
        if (w1[i] == w2[j]) return memo[key] = dfs(w1, w2, i + 1, j + 1);
        return memo[key] = 1 + min(dfs(w1, w2, i + 1, j), dfs(w1, w2, i, j + 1));
    }
public:
    int minDistance(string word1, string word2) {
        memo.clear();
        return dfs(word1, word2, 0, 0);
    }
};

int main() {
    Solution sol;
    cout << sol.minDistance("sea", "eat") << endl; // 2
    return 0;
}

Line Notes

unordered_map<string, int> memo;Cache for memoization

string key = to_string(i) + "," + to_string(j);Unique key for memo

if (memo.count(key))Return cached result if exists

memo[key] = w2.size() - j;Base case: delete remaining chars in word2

memo[key] = w1.size() - i;Base case: delete remaining chars in word1

memo[key] = 1 + min(...)Store result after deleting one char

function minDistance(word1, word2) {
    const memo = new Map();
    function dfs(i, j) {
        const key = i + ',' + j;
        if (memo.has(key)) return memo.get(key);
        if (i === word1.length) {
            memo.set(key, word2.length - j);
            return memo.get(key);
        }
        if (j === word2.length) {
            memo.set(key, word1.length - i);
            return memo.get(key);
        }
        let res;
        if (word1[i] === word2[j]) {
            res = dfs(i + 1, j + 1);
        } else {
            res = 1 + Math.min(dfs(i + 1, j), dfs(i, j + 1));
        }
        memo.set(key, res);
        return res;
    }
    return dfs(0, 0);
}

console.log(minDistance('sea', 'eat')); // 2

Line Notes

const memo = new Map();Cache to store computed results

const key = i + ',' + j;Unique key for memoization

if (memo.has(key))Return cached result if available

memo.set(key, word2.length - j);Base case: delete remaining chars in word2

memo.set(key, word1.length - i);Base case: delete remaining chars in word1

memo.set(key, res);Store computed result before returning

⏱

Complexity

TimeO(m*n)

SpaceO(m*n) for memo and recursion stack

Each subproblem (i,j) is computed once and stored.

💡 For strings of length 100, this means 10,000 computations, which is efficient.

Interview Verdict: Accepted

Memoization makes the solution efficient enough for interview constraints.

🧠

Bottom-Up DP (Tabulation)

💡 Tabulation builds the solution iteratively from smaller subproblems, which is often easier to debug and understand than recursion.

Intuition

Fill a 2D table dp where dp[i][j] represents minimal deletions for suffixes starting at i and j, starting from the ends of the strings.

Algorithm

1. Initialize dp array of size (m+1) x (n+1).
2. Fill base cases: dp[m][j] = length of suffix of word2, dp[i][n] = length of suffix of word1.
3. Iterate i from m-1 down to 0 and j from n-1 down to 0.
4. If characters match, dp[i][j] = dp[i+1][j+1].
5. Else dp[i][j] = 1 + min(dp[i+1][j], dp[i][j+1]).
6. Return dp[0][0] as the answer.

💡 This approach explicitly fills the DP table in a safe order ensuring all dependencies are computed before use.

Recurrence:dp[i][j] = if word1[i] == word2[j] then dp[i+1][j+1] else 1 + min(dp[i+1][j], dp[i][j+1])

</>

Code

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

# Example usage
if __name__ == '__main__':
    print(minDistance('sea', 'eat'))  # Output: 2

Line Notes

dp = [[0] * (n + 1) for _ in range(m + 1)]Create DP table with extra row and column for base cases

dp[i][n] = m - iIf word2 exhausted, delete remaining chars in word1

dp[m][j] = n - jIf word1 exhausted, delete remaining chars in word2

for i in range(m - 1, -1, -1)Fill dp from bottom to top

if word1[i] == word2[j]If chars match, no deletion needed

dp[i][j] = 1 + min(...)Delete one char from either string

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][n] = m - i;
        for (int j = 0; j <= n; j++) dp[m][j] = n - j;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (word1.charAt(i) == word2.charAt(j)) {
                    dp[i][j] = dp[i + 1][j + 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        return dp[0][0];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minDistance("sea", "eat")); // 2
    }
}

Line Notes

int[][] dp = new int[m + 1][n + 1];DP table with extra row and column for base cases

dp[i][n] = m - i;Base case: delete remaining chars in word1

dp[m][j] = n - j;Base case: delete remaining chars in word2

for (int i = m - 1; i >= 0; i--)Fill dp bottom-up

if (word1.charAt(i) == word2.charAt(j))If chars match, no deletion needed

dp[i][j] = 1 + Math.min(...)Delete one char from either string

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

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 0; i <= m; i++) dp[i][n] = m - i;
        for (int j = 0; j <= n; j++) dp[m][j] = n - j;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (word1[i] == word2[j]) dp[i][j] = dp[i + 1][j + 1];
                else dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j + 1]);
            }
        }
        return dp[0][0];
    }
};

int main() {
    Solution sol;
    cout << sol.minDistance("sea", "eat") << endl; // 2
    return 0;
}

Line Notes

vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));DP table with base cases

dp[i][n] = m - i;Delete remaining chars in word1 if word2 exhausted

dp[m][j] = n - j;Delete remaining chars in word2 if word1 exhausted

for (int i = m - 1; i >= 0; i--)Fill dp bottom-up

if (word1[i] == word2[j])No deletion if chars match

dp[i][j] = 1 + min(...)Delete one char from either string

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

console.log(minDistance('sea', 'eat')); // 2

Line Notes

const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));Initialize DP table with zeros

dp[i][n] = m - i;Base case: delete remaining chars in word1

dp[m][j] = n - j;Base case: delete remaining chars in word2

for (let i = m - 1; i >= 0; i--)Fill dp bottom-up

if (word1[i] === word2[j])No deletion if chars match

dp[i][j] = 1 + Math.min(...)Delete one char from either string

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We fill a 2D table of size m*n once.

💡 For strings of length 100, this means 10,000 operations, which is efficient.

Interview Verdict: Accepted

This is the standard DP solution for this problem and is optimal in time complexity.

🧠

Space Optimized Bottom-Up DP

💡 Since dp[i][j] depends only on dp[i+1][j], dp[i][j+1], and dp[i+1][j+1], we can reduce space from O(m*n) to O(n) by storing only one row at a time.

Intuition

Use a single 1D array to represent the current row and update it from right to left to preserve needed values.

Algorithm

1. Initialize a 1D dp array of length n+1 representing the last row.
2. Fill dp with base case values for empty word1 suffix.
3. Iterate i from m-1 down to 0:
4. Keep a variable prev to store dp[j+1] from previous iteration.
5. Iterate j from n-1 down to 0:
6. Save current dp[j] in temp before updating.
7. If chars match, dp[j] = prev; else dp[j] = 1 + min(dp[j], dp[j+1]).
8. Update prev = temp for next iteration.
9. Return dp[0] as the answer.

💡 Reverse iteration ensures dp[j+1] and prev hold correct values before update, preserving correctness.

Recurrence:dp[j] = if word1[i] == word2[j] then prev else 1 + min(dp[j], dp[j+1])

</>

Code

def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [0] * (n + 1)
    for j in range(n + 1):
        dp[j] = n - j
    for i in range(m - 1, -1, -1):
        prev = dp[n]
        dp[n] = m - i
        for j in range(n - 1, -1, -1):
            temp = dp[j]
            if word1[i] == word2[j]:
                dp[j] = prev
            else:
                dp[j] = 1 + min(dp[j], dp[j + 1])
            prev = temp
    return dp[0]

# Example usage
if __name__ == '__main__':
    print(minDistance('sea', 'eat'))  # Output: 2

Line Notes

dp = [0] * (n + 1)Initialize 1D DP array for last row

for j in range(n + 1): dp[j] = n - jBase case: delete remaining chars in word2

prev = dp[n]Store dp[j+1] from previous iteration (diagonal)

dp[n] = m - iBase case: delete remaining chars in word1

temp = dp[j]Save current dp[j] before update

dp[j] = prevIf chars match, take diagonal value

dp[j] = 1 + min(dp[j], dp[j + 1])If chars differ, delete one char

prev = tempUpdate prev for next iteration

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[] dp = new int[n + 1];
        for (int j = 0; j <= n; j++) dp[j] = n - j;
        for (int i = m - 1; i >= 0; i--) {
            int prev = dp[n];
            dp[n] = m - i;
            for (int j = n - 1; j >= 0; j--) {
                int temp = dp[j];
                if (word1.charAt(i) == word2.charAt(j)) {
                    dp[j] = prev;
                } else {
                    dp[j] = 1 + Math.min(dp[j], dp[j + 1]);
                }
                prev = temp;
            }
        }
        return dp[0];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minDistance("sea", "eat")); // 2
    }
}

Line Notes

int[] dp = new int[n + 1];1D DP array for last row

for (int j = 0; j <= n; j++) dp[j] = n - j;Base case for empty word1 suffix

int prev = dp[n];Store diagonal value before update

dp[n] = m - i;Base case for empty word2 suffix

int temp = dp[j];Save current dp[j] before update

dp[j] = prev;If chars match, take diagonal value

dp[j] = 1 + Math.min(...)If chars differ, delete one char

prev = temp;Update prev for next iteration

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

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<int> dp(n + 1, 0);
        for (int j = 0; j <= n; j++) dp[j] = n - j;
        for (int i = m - 1; i >= 0; i--) {
            int prev = dp[n];
            dp[n] = m - i;
            for (int j = n - 1; j >= 0; j--) {
                int temp = dp[j];
                if (word1[i] == word2[j]) dp[j] = prev;
                else dp[j] = 1 + min(dp[j], dp[j + 1]);
                prev = temp;
            }
        }
        return dp[0];
    }
};

int main() {
    Solution sol;
    cout << sol.minDistance("sea", "eat") << endl; // 2
    return 0;
}

Line Notes

vector<int> dp(n + 1, 0);1D DP array for last row

for (int j = 0; j <= n; j++) dp[j] = n - j;Base case for empty word1 suffix

int prev = dp[n];Store diagonal value before update

dp[n] = m - i;Base case for empty word2 suffix

int temp = dp[j];Save current dp[j] before update

dp[j] = prev;If chars match, take diagonal value

dp[j] = 1 + min(...)If chars differ, delete one char

prev = temp;Update prev for next iteration

function minDistance(word1, word2) {
    const m = word1.length, n = word2.length;
    const dp = new Array(n + 1).fill(0);
    for (let j = 0; j <= n; j++) dp[j] = n - j;
    for (let i = m - 1; i >= 0; i--) {
        let prev = dp[n];
        dp[n] = m - i;
        for (let j = n - 1; j >= 0; j--) {
            let temp = dp[j];
            if (word1[i] === word2[j]) {
                dp[j] = prev;
            } else {
                dp[j] = 1 + Math.min(dp[j], dp[j + 1]);
            }
            prev = temp;
        }
    }
    return dp[0];
}

console.log(minDistance('sea', 'eat')); // 2

Line Notes

const dp = new Array(n + 1).fill(0);Initialize 1D DP array

for (let j = 0; j <= n; j++) dp[j] = n - j;Base case for empty word1 suffix

let prev = dp[n];Store diagonal value before update

dp[n] = m - i;Base case for empty word2 suffix

let temp = dp[j];Save current dp[j] before update

dp[j] = prev;If chars match, take diagonal value

dp[j] = 1 + Math.min(...)If chars differ, delete one char

prev = temp;Update prev for next iteration

⏱

Complexity

TimeO(m*n)

SpaceO(n)

Only one row of DP is stored and updated iteratively.

💡 This reduces memory usage significantly for large inputs.

Interview Verdict: Accepted

This is the most space-efficient DP solution suitable for large inputs.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the bottom-up DP or space optimized DP is usually best for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^(m+n))	O(m+n) recursion stack	Yes (deep recursion)	No	Mention only - never code
2. Top-Down DP with Memoization	O(m*n)	O(m*n) memo + recursion stack	Possible for large inputs	Yes	Good for quick optimization of brute force
3. Bottom-Up DP (Tabulation)	O(m*n)	O(m*n)	No	Yes	Standard approach to code in interviews
4. Space Optimized Bottom-Up DP	O(m*n)	O(n)	No	No (without extra work)	Mention if asked about optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and examples.Step 2: Present brute force recursion to show understanding.Step 3: Introduce memoization to optimize recursion.Step 4: Explain bottom-up DP for iterative solution.Step 5: Discuss space optimization if time permits.Step 6: Code the chosen approach carefully.Step 7: Test with edge cases and explain complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Understanding of DP state definition, ability to optimize recursion, clarity in explaining recurrence, and coding accuracy.

Common Follow-ups

• What if insertions are allowed? → Leads to Edit Distance problem.
• Can you reconstruct the common subsequence? → Use DP table to backtrack.
• How to handle very large strings? → Use space optimized DP.
• What if deletions have different costs? → Modify DP to include weights.

💡 These follow-ups test deeper understanding and ability to adapt the solution.

🔍

Pattern Recognition

When to Use

1) Problem involves two strings; 2) Need minimal operations to make strings equal; 3) Only deletions allowed; 4) Overlapping subproblems with optimal substructure.

Signature Phrases

'minimum number of steps to make two strings the same''delete exactly one character in either string'

NOT This Pattern When

Problems involving only insertions or replacements without deletions, or those solvable greedily.

Similar Problems

Longest Common Subsequence - core concept underlying minimal deletionsEdit Distance - extends to insertions and replacementsMinimum ASCII Delete Sum for Two Strings - weighted deletion costs

Practice

1. The following code attempts to implement the space-optimized DP for longest common substring. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def longest_common_substring_space_optimized_buggy(s1, s2):
    n, m = len(s1), len(s2)
    dp = [0] * (m + 1)
    max_len = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):  # Note: iterating forward
            if s1[i - 1] == s2[j - 1]:
                dp[j] = dp[j - 1] + 1
                if dp[j] > max_len:
                    max_len = dp[j]
            else:
                dp[j] = 0
    return max_len

medium

A. Line with 'dp[j] = dp[j - 1] + 1' updating dp

B. Line with 'dp = [0] * (m + 1)' initializing dp array

C. Line with 'if dp[j] > max_len:' updating max_len

D. Line with 'for j in range(1, m + 1):' iterating forward

Solution

1. Step 1: Understand dp array update dependency

   dp[j] depends on dp[j-1] from previous iteration of inner loop, so iterating forward overwrites dp[j-1] before use.

2. Step 2: Identify iteration order bug

   Iterating j forward causes dp[j-1] to be updated before dp[j], corrupting the chain of matching lengths.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Changing inner loop to iterate backward fixes the bug [OK]

Hint: DP update depends on previous dp[j-1], so iterate backward [OK]

Common Mistakes:

• Updating dp forward overwrites needed values
• Incorrect max_len update timing
• Wrong dp initialization size

2. Identify the bug in the following space-optimized DP code for longest palindromic subsequence:

medium

A. Line updating dp[j] inside the inner loop

B. Line updating prev variable

C. Line initializing dp with zeros instead of ones

D. Line comparing s[i] and s[j]

Solution

1. Step 1: Check dp initialization

   dp should be initialized with 1s because every single character is a palindrome of length 1.

2. Step 2: Consequence of zero initialization

   Initializing dp with zeros causes palindromes of length 1 to be counted as 0, leading to incorrect results.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct initialization is dp = [1]*n, not zeros [OK]

Hint: dp[i][i] = 1 base case must be set [OK]

Common Mistakes:

• Forgetting base case initialization
• Overwriting dp too early
• Misusing prev variable

3. The following code attempts to compute the minimum cuts needed for palindrome partitioning. Identify the line containing the subtle bug that can cause incorrect results or index errors.

medium

A. Line where dp[right] is updated using dp[left] + 1 instead of dp[left - 1] + 1

B. Line where left and right pointers are initialized for even length palindromes

C. Line where dp is initialized with zeros instead of incremental indices

D. Line where the function returns dp[-1]

Solution

1. Step 1: Analyze dp initialization

   Initializing dp with zeros is incorrect but not the subtle bug asked; it causes incorrect min cuts but no crash.

2. Step 2: Check dp update line

   Using dp[left] + 1 instead of dp[left - 1] + 1 causes off-by-one error and possible index out of bounds when left=0.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct dp update requires dp[left - 1] + 1 to count cuts before palindrome start [OK]

Hint: Check dp update indices carefully for off-by-one errors [OK]

Common Mistakes:

• Using dp[left] instead of dp[left - 1]
• Initializing dp with zeros instead of incremental indices
• Ignoring even length palindrome expansions

4. Suppose you want to find the length of the longest common subsequence between two strings, but now characters from the second string can be reused multiple times. Which modification to the standard LCS algorithm correctly handles this scenario?

hard

A. Use the same DP but allow dp[j] to depend on dp[j] itself without decrementing j in inner loop

B. Change the inner loop to iterate forwards and update dp[j] using dp[j] and dp[j-1] to allow reuse

C. Use a greedy approach matching characters from left to right allowing reuse

D. Use a bottom-up DP with a 2D table but ignore previous matches to allow reuse

Solution

1. Step 1: Understand reuse impact

   Allowing reuse of characters in the second string means dp[j] can be updated based on dp[j] itself (not only dp[j-1]) and the inner loop must run forwards to propagate reuse correctly.

2. Step 2: Identify correct DP iteration

   Iterating forwards in the inner loop allows dp[j] to accumulate matches with reuse, unlike standard LCS which iterates backwards to avoid reuse.

3. Step 3: Evaluate other options

   Greedy fails to find optimal subsequence. Ignoring previous matches breaks DP correctness. Using 2D DP without reuse logic is insufficient.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Forward iteration in inner loop enables reuse of characters [OK]

Hint: Forward inner loop iteration enables reuse in DP [OK]

Common Mistakes:

• Using backward iteration preventing reuse
• Trying greedy approach
• Ignoring DP state dependencies

5. Suppose the problem is modified so that each integer in nums1 and nums2 can be used multiple times to form uncrossed lines (i.e., reuse allowed). Which of the following algorithmic changes correctly adapts the solution?

hard

A. Modify the DP to consider unlimited reuse by allowing transitions that do not increment both indices simultaneously after a match

B. Change the DP to allow staying on the same index in nums1 or nums2 after a match, effectively converting to a longest common substring problem

C. Use a greedy approach to connect all matching pairs regardless of crossing

D. Use the same DP but allow matching the same indices multiple times by removing the increment of i and j after a match

Solution

1. Step 1: Understand reuse implications

   Allowing reuse means after matching nums1[i] and nums2[j], we can match nums1[i] or nums2[j] again, so indices may not both increment.

2. Step 2: Adapt DP transitions

   The DP must allow transitions that increment only one index or none after a match, unlike classic LCS where both indices increment. This requires modifying the recurrence to consider reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Allowing reuse requires DP transitions that do not always increment both indices [OK]

Hint: Reuse means indices may not both advance after a match [OK]

Common Mistakes:

• Removing increments without adjusting DP
• Confusing reuse with substring problem
• Using greedy approach ignoring crossing