Longest Common Subsequence

🎯

Longest Common Subsequence

mediumDPAmazonGoogleMicrosoft

Imagine comparing two versions of a document to find the longest sequence of words that appear in both, preserving order but not necessarily contiguity.

💡 This problem is a classic example of dynamic programming on strings. Beginners often struggle because the problem requires understanding how to break down sequences into subproblems and how to handle overlapping subproblems efficiently.

📋

Problem Statement

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. If there is no common subsequence, return 0.

1 ≤ text1.length, text2.length ≤ 10^5text1 and text2 consist of only lowercase English letters.

💡

Example

Input"text1 = \"abcde\", text2 = \"ace\""

Output3

The longest common subsequence is "ace" and its length is 3.

Input"text1 = \"abc\", text2 = \"abc\""

Output3

The longest common subsequence is "abc" itself.

Input"text1 = \"abc\", text2 = \"def\""

Output0

There is no common subsequence.

• One or both strings are empty → output 0
• Strings with no common characters → output 0
• Strings are identical → output length of either string
• Strings with repeated characters → ensure subsequence counts correctly

🔁

Why DP?

Why greedy fails:

A greedy approach might try to match characters as soon as they appear, but this fails. For example, text1 = "abcde", text2 = "aed". Greedy would match 'a' then 'e' then 'd' in order, but the longest common subsequence is actually "ad" (length 2), not 3, because 'e' appears after 'd' in text1, so the greedy approach overestimates.

DP state:

dp[i][j] represents the length of the longest common subsequence between the first i characters of text1 and the first j characters of text2.

Recurrence: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])

If the current characters match, add 1 to the LCS of the previous prefixes; otherwise, take the maximum LCS by skipping one character from either string.

⚠️

Common Mistakes

Not handling base cases correctly

Index errors or incorrect results for empty strings

✅ Initialize dp arrays with size (m+1)*(n+1) and set dp[0][*] and dp[*][0] to 0

Mixing up indices (off-by-one errors)

Wrong character comparisons and incorrect dp updates

✅ Remember dp indices are 1-based for prefixes; string indices are 0-based

Not iterating backwards in space optimized approach

Overwrites dp[j-1] before it is used, causing wrong results

✅ Iterate j from n down to 1 when updating dp array

Using greedy approach to match characters

Incorrect LCS length for some inputs

✅ Use DP to consider all subsequence possibilities

Not caching results in memoization

Solution runs as slow as brute force

✅ Store computed results in memo table and check before recursion

🧠

Brute Force (Pure Recursion)

💡 This approach helps understand the problem's recursive structure and why naive solutions are inefficient due to repeated computations.

Intuition

Try all subsequences by recursively checking if characters match or skipping characters in either string, then take the maximum length found.

Algorithm

1. If either string is empty, return 0.
2. If last characters of both strings match, add 1 and recurse on remaining prefixes.
3. Otherwise, recurse by skipping last character of either string and take max result.
4. Return the maximum length found.

💡 The recursion explores all combinations, which is conceptually simple but computationally expensive.

Recurrence:lcs(i, j) = 1 + lcs(i-1, j-1) if text1[i-1] == text2[j-1], else max(lcs(i-1, j), lcs(i, j-1))

</>

Code

def lcs(text1, text2, i, j):
    if i == 0 or j == 0:
        return 0
    if text1[i-1] == text2[j-1]:
        return 1 + lcs(text1, text2, i-1, j-1)
    else:
        return max(lcs(text1, text2, i-1, j), lcs(text1, text2, i, j-1))

# Driver code
text1 = "abcde"
text2 = "ace"
print(lcs(text1, text2, len(text1), len(text2)))

Line Notes

if i == 0 or j == 0:Base case: empty string means no common subsequence

if text1[i-1] == text2[j-1]:Check if last characters match to extend subsequence

return 1 + lcs(text1, text2, i-1, j-1)Add 1 and recurse on smaller prefixes

return max(lcs(text1, text2, i-1, j), lcs(text1, text2, i, j-1))Try skipping one character from either string

public class Solution {
    public static int lcs(String text1, String text2, int i, int j) {
        if (i == 0 || j == 0) return 0;
        if (text1.charAt(i - 1) == text2.charAt(j - 1))
            return 1 + lcs(text1, text2, i - 1, j - 1);
        else
            return Math.max(lcs(text1, text2, i - 1, j), lcs(text1, text2, i, j - 1));
    }

    public static void main(String[] args) {
        String text1 = "abcde";
        String text2 = "ace";
        System.out.println(lcs(text1, text2, text1.length(), text2.length()));
    }
}

Line Notes

if (i == 0 || j == 0) return 0;Base case for empty prefix

if (text1.charAt(i - 1) == text2.charAt(j - 1))Check last characters for match

return 1 + lcs(text1, text2, i - 1, j - 1);Add 1 and recurse on smaller prefixes

return Math.max(lcs(text1, text2, i - 1, j), lcs(text1, text2, i, j - 1));Try skipping one character from either string

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

int lcs(const string &text1, const string &text2, int i, int j) {
    if (i == 0 || j == 0) return 0;
    if (text1[i - 1] == text2[j - 1])
        return 1 + lcs(text1, text2, i - 1, j - 1);
    else
        return max(lcs(text1, text2, i - 1, j), lcs(text1, text2, i, j - 1));
}

int main() {
    string text1 = "abcde";
    string text2 = "ace";
    cout << lcs(text1, text2, text1.size(), text2.size()) << endl;
    return 0;
}

Line Notes

if (i == 0 || j == 0) return 0;Base case: no characters left means no subsequence

if (text1[i - 1] == text2[j - 1])Check if last characters match

return 1 + lcs(text1, text2, i - 1, j - 1);Add 1 and recurse on smaller prefixes

return max(lcs(text1, text2, i - 1, j), lcs(text1, text2, i, j - 1));Try skipping one character from either string

function lcs(text1, text2, i, j) {
    if (i === 0 || j === 0) return 0;
    if (text1[i - 1] === text2[j - 1]) {
        return 1 + lcs(text1, text2, i - 1, j - 1);
    } else {
        return Math.max(lcs(text1, text2, i - 1, j), lcs(text1, text2, i, j - 1));
    }
}

// Driver code
const text1 = "abcde";
const text2 = "ace";
console.log(lcs(text1, text2, text1.length, text2.length));

Line Notes

if (i === 0 || j === 0) return 0;Base case for empty substring

if (text1[i - 1] === text2[j - 1]) {Check if last characters match

return 1 + lcs(text1, text2, i - 1, j - 1);Add 1 and recurse on smaller prefixes

return Math.max(lcs(text1, text2, i - 1, j), lcs(text1, text2, i, j - 1));Try skipping one character from either string

⏱

Complexity

TimeO(2^(m+n))

SpaceO(m+n) due to recursion stack

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

💡 For strings of length 20, this approach can cause 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 Memoization

💡 Memoization avoids recomputing the same subproblems by caching results, drastically improving efficiency.

Intuition

Use recursion like brute force but store results of subproblems in a table to reuse them when needed.

Algorithm

1. Initialize a 2D cache with -1 indicating uncomputed states.
2. Recursively compute LCS length for prefixes, returning cached results if available.
3. If characters match, add 1 plus result from smaller prefixes.
4. Otherwise, take max of skipping one character from either string.

💡 Memoization transforms exponential recursion into polynomial time by avoiding repeated work.

Recurrence:Same as brute force: lcs(i, j) = 1 + lcs(i-1, j-1) if match else max(lcs(i-1, j), lcs(i, j-1))

</>

Code

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    memo = [[-1] * (n + 1) for _ in range(m + 1)]

    def dfs(i, j):
        if i == 0 or j == 0:
            return 0
        if memo[i][j] != -1:
            return memo[i][j]
        if text1[i - 1] == text2[j - 1]:
            memo[i][j] = 1 + dfs(i - 1, j - 1)
        else:
            memo[i][j] = max(dfs(i - 1, j), dfs(i, j - 1))
        return memo[i][j]

    return dfs(m, n)

# Driver code
print(lcs("abcde", "ace"))

Line Notes

memo = [[-1] * (n + 1) for _ in range(m + 1)]Initialize memo table with -1 to mark unvisited states

if memo[i][j] != -1:Return cached result if already computed

if text1[i - 1] == text2[j - 1]:Check if characters match to extend subsequence

memo[i][j] = max(dfs(i - 1, j), dfs(i, j - 1))Store max result after skipping one character

public class Solution {
    public static int lcs(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] memo = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++)
            for (int j = 0; j <= n; j++)
                memo[i][j] = -1;
        return dfs(text1, text2, m, n, memo);
    }

    private static int dfs(String text1, String text2, int i, int j, int[][] memo) {
        if (i == 0 || j == 0) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        if (text1.charAt(i - 1) == text2.charAt(j - 1))
            memo[i][j] = 1 + dfs(text1, text2, i - 1, j - 1, memo);
        else
            memo[i][j] = Math.max(dfs(text1, text2, i - 1, j, memo), dfs(text1, text2, i, j - 1, memo));
        return memo[i][j];
    }

    public static void main(String[] args) {
        System.out.println(lcs("abcde", "ace"));
    }
}

Line Notes

int[][] memo = new int[m + 1][n + 1];Create memo table for caching

if (memo[i][j] != -1) return memo[i][j];Return cached result if available

if (text1.charAt(i - 1) == text2.charAt(j - 1))Check for character match

memo[i][j] = Math.max(...)Store max result after skipping characters

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

int dfs(const string &text1, const string &text2, int i, int j, vector<vector<int>> &memo) {
    if (i == 0 || j == 0) return 0;
    if (memo[i][j] != -1) return memo[i][j];
    if (text1[i - 1] == text2[j - 1])
        memo[i][j] = 1 + dfs(text1, text2, i - 1, j - 1, memo);
    else
        memo[i][j] = max(dfs(text1, text2, i - 1, j, memo), dfs(text1, text2, i, j - 1, memo));
    return memo[i][j];
}

int lcs(const string &text1, const string &text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> memo(m + 1, vector<int>(n + 1, -1));
    return dfs(text1, text2, m, n, memo);
}

int main() {
    cout << lcs("abcde", "ace") << endl;
    return 0;
}

Line Notes

vector<vector<int>> memo(m + 1, vector<int>(n + 1, -1));Initialize memo table with -1

if (memo[i][j] != -1) return memo[i][j];Return cached result if computed

if (text1[i - 1] == text2[j - 1])Check character match

memo[i][j] = max(...)Store max LCS length after skipping characters

function lcs(text1, text2) {
    const m = text1.length, n = text2.length;
    const memo = Array.from({ length: m + 1 }, () => Array(n + 1).fill(-1));

    function dfs(i, j) {
        if (i === 0 || j === 0) return 0;
        if (memo[i][j] !== -1) return memo[i][j];
        if (text1[i - 1] === text2[j - 1]) {
            memo[i][j] = 1 + dfs(i - 1, j - 1);
        } else {
            memo[i][j] = Math.max(dfs(i - 1, j), dfs(i, j - 1));
        }
        return memo[i][j];
    }

    return dfs(m, n);
}

console.log(lcs("abcde", "ace"));

Line Notes

const memo = Array.from({ length: m + 1 }, () => Array(n + 1).fill(-1));Create 2D memo array initialized to -1

if (memo[i][j] !== -1) return memo[i][j];Return cached result if available

if (text1[i - 1] === text2[j - 1]) {Check if characters match

memo[i][j] = Math.max(dfs(i - 1, j), dfs(i, j - 1));Store max LCS length after skipping characters

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

Each subproblem (i,j) is computed once and stored, reducing exponential calls to polynomial.

💡 For strings of length 1000, this means about 1 million computations, which is feasible.

Interview Verdict: Accepted

Memoization makes the solution efficient enough for typical interview constraints.

🧠

Bottom-Up Tabulation

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

Intuition

Fill a 2D dp table where each cell represents the LCS length for prefixes of the two strings, using previously computed values.

Algorithm

1. Create a 2D dp array of size (m+1) x (n+1) initialized to 0.
2. Iterate over each character of text1 (rows) and text2 (columns).
3. If characters match, set dp[i][j] = 1 + dp[i-1][j-1].
4. Otherwise, set dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
5. Return dp[m][n] as the final answer.

💡 This approach systematically builds up the solution from the smallest subproblems to the full problem.

Recurrence:dp[i][j] = 1 + dp[i-1][j-1] if text1[i-1] == text2[j-1] else max(dp[i-1][j], dp[i][j-1])

</>

Code

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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]

# Driver code
print(lcs("abcde", "ace"))

Line Notes

dp = [[0] * (n + 1) for _ in range(m + 1)]Initialize dp table with zeros for base cases

for i in range(1, m + 1):Iterate over prefixes of text1

if text1[i - 1] == text2[j - 1]:Check if characters match to extend LCS

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])Take max by skipping one character

public class Solution {
    public static int lcs(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1))
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(lcs("abcde", "ace"));
    }
}

Line Notes

int[][] dp = new int[m + 1][n + 1];Create dp table with base zeros

for (int i = 1; i <= m; i++) {Loop over prefixes of text1

if (text1.charAt(i - 1) == text2.charAt(j - 1))Check character match

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);Choose max skipping one character

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

int lcs(const string &text1, const string &text2) {
    int m = text1.size(), n = text2.size();
    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 main() {
    cout << lcs("abcde", "ace") << endl;
    return 0;
}

Line Notes

vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));Initialize dp table with zeros

for (int i = 1; i <= m; i++) {Iterate over prefixes of text1

if (text1[i - 1] == text2[j - 1])Check for character match

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);Choose max skipping one character

function lcs(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let 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] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

console.log(lcs("abcde", "ace"));

Line Notes

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

for (let i = 1; i <= m; i++) {Loop over prefixes of text1

if (text1[i - 1] === text2[j - 1]) {Check if characters match

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);Choose max skipping one character

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We fill a table of size m*n once, each cell computed in O(1).

💡 This approach is efficient and practical for typical interview input sizes.

Interview Verdict: Accepted

This is the standard DP solution expected in interviews.

🧠

Space Optimized Bottom-Up DP

💡 Since dp[i][j] depends only on dp[i-1][j-1], dp[i-1][j], and dp[i][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 previous row and update it iteratively, carefully preserving needed values.

Algorithm

1. Initialize a 1D dp array of length n+1 with zeros.
2. Iterate over each character of text1.
3. For each character of text2, iterate backwards to update dp[j] using dp[j-1] and previous dp[j].
4. If characters match, dp[j] = 1 + prev (dp[j-1] from previous iteration).
5. Otherwise, dp[j] = max(dp[j], dp[j-1]). Return dp[n] as result.

💡 Backward iteration prevents overwriting values needed for current computation, enabling correct updates in 1D.

Recurrence:dp[j] = 1 + prev if match else max(dp[j], dp[j-1])

</>

Code

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [0] * (n + 1)
    for i in range(1, m + 1):
        prev = 0
        for j in range(n, 0, -1):
            temp = dp[j]
            if text1[i - 1] == text2[j - 1]:
                dp[j] = 1 + prev
            else:
                dp[j] = max(dp[j], dp[j - 1])
            prev = temp
    return dp[n]

# Driver code
print(lcs("abcde", "ace"))

Line Notes

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

prev = 0Stores dp[j-1] from previous iteration

temp = dp[j]Temporarily store current dp[j] before update

dp[j] = 1 + prevUpdate dp[j] when characters match using previous diagonal

public class Solution {
    public static int lcs(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[] dp = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            int prev = 0;
            for (int j = n; j >= 1; j--) {
                int temp = dp[j];
                if (text1.charAt(i - 1) == text2.charAt(j - 1))
                    dp[j] = 1 + prev;
                else
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                prev = temp;
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(lcs("abcde", "ace"));
    }
}

Line Notes

int[] dp = new int[n + 1];1D dp array to store previous row results

int prev = 0;Stores dp[j-1] from previous iteration

int temp = dp[j];Temporarily hold dp[j] before update

dp[j] = 1 + prev;Update dp[j] when characters match

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

int lcs(const string &text1, const string &text2) {
    int m = text1.size(), n = text2.size();
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= m; i++) {
        int prev = 0;
        for (int j = n; j >= 1; j--) {
            int temp = dp[j];
            if (text1[i - 1] == text2[j - 1])
                dp[j] = 1 + prev;
            else
                dp[j] = max(dp[j], dp[j - 1]);
            prev = temp;
        }
    }
    return dp[n];
}

int main() {
    cout << lcs("abcde", "ace") << endl;
    return 0;
}

Line Notes

vector<int> dp(n + 1, 0);Initialize 1D dp vector

int prev = 0;Stores dp[j-1] from previous iteration

int temp = dp[j];Temporarily hold dp[j] before update

dp[j] = 1 + prev;Update dp[j] when characters match

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

console.log(lcs("abcde", "ace"));

Line Notes

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

let prev = 0;Stores dp[j-1] from previous iteration

let temp = dp[j];Temporarily hold dp[j] before update

dp[j] = 1 + prev;Update dp[j] when characters match

⏱

Complexity

TimeO(m*n)

SpaceO(n)

We use a single array of length n and update it for each character of text1.

💡 This reduces memory usage significantly while maintaining time efficiency.

Interview Verdict: Accepted

This is the most memory-efficient DP solution commonly accepted in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the bottom-up tabulation or space optimized DP is usually best; brute force is only for explanation.

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 practical	Mention only - never code
2. Top-Down Memoization	O(m*n)	O(m*n)	Possible for large inputs	Yes	Good for explaining optimization
3. Bottom-Up Tabulation	O(m*n)	O(m*n)	No	Yes	Standard solution to code
4. Space Optimized DP	O(m*n)	O(n)	No	Harder, but possible with extra logic	Mention or code if asked for optimization

💼

Interview Strategy

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

How to Present

Clarify problem constraints and definitions.Explain brute force recursion to show problem structure.Introduce memoization to optimize overlapping subproblems.Present bottom-up tabulation as the standard DP solution.Optionally discuss space optimization for memory efficiency.Write clean code and test with edge cases.

Time Allocation

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

What the Interviewer Tests

Understanding of recursion and DP, ability to optimize naive solutions, code correctness, and handling edge cases.

Common Follow-ups

• How to reconstruct the actual LCS string? → Use backtracking from dp table.
• Can we optimize space? → Yes, use 1D dp array with careful iteration.
• What if strings are very long? → Use space optimized DP or heuristic methods.
• How to handle multiple LCS of same length? → Backtracking can find all.

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

🔍

Pattern Recognition

When to Use

1) Problem involves two sequences; 2) Need to find longest matching subsequence; 3) Order matters but not contiguity; 4) Overlapping subproblems exist.

Signature Phrases

"longest common subsequence""subsequence""not necessarily contiguous""preserving order"

NOT This Pattern When

Longest Common Substring - requires contiguous matching characters, solved differently.

Similar Problems

Edit Distance - also uses DP on two strings but focuses on transformationsLongest Palindromic Subsequence - LCS variant on one stringShortest Common Supersequence - combines two sequences minimally

Practice

1. You are given two strings and want to find the minimum number of delete operations needed to make them equal. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming based on Longest Common Subsequence (LCS)

B. Greedy approach deleting mismatched characters as soon as found

C. Pure brute force recursion without memoization

D. Sorting both strings and comparing characters sequentially

Solution

1. Step 1: Understand problem requires minimal deletions to equalize strings

   This is equivalent to finding the longest common subsequence (LCS) and deleting characters not in it.

2. Step 2: Recognize DP approach based on LCS guarantees optimal solution

   Greedy or sorting approaches fail because they do not consider subsequence order; brute force is correct but inefficient.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   LCS-based DP is classic for minimal delete operations [OK]

Hint: Minimal deletes -> LCS-based DP [OK]

Common Mistakes:

• Thinking greedy deletion works optimally
• Ignoring subsequence order
• Confusing sorting with subsequence

2. What is the time complexity of the space-optimized bottom-up DP solution for the Delete Operation for Two Strings problem, where the input strings have lengths m and n respectively?

medium

A. O(m * n)

B. O(m + n)

C. O(m * n * log(m + n))

D. O(m^2 + n^2)

Solution

1. Step 1: Identify nested loops over m and n

   The outer loop runs m times, inner loop runs n times, leading to m*n iterations.

2. Step 2: Confirm no extra hidden factors

   Each iteration does O(1) work; no sorting or recursion overhead.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP table size m*n and each cell computed once [OK]

Hint: Nested loops over m and n -> O(m*n) [OK]

Common Mistakes:

• Confusing linear with quadratic
• Assuming sorting or recursion adds log factor
• Ignoring nested loops

3. 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

4. What is the time and space complexity of the space-optimized bottom-up DP solution for the longest palindromic subsequence problem on a string of length n?

medium

A. Time: O(n^2), Space: O(n)

B. Time: O(n), Space: O(n^2)

C. Time: O(n^3), Space: O(n)

D. Time: O(n^2), Space: O(n^2)

Solution

1. Step 1: Identify nested loops over indices i and j

   Outer loop runs n times, inner loop up to n times -> O(n^2) time.

2. Step 2: Analyze space usage

   Space optimized DP uses a single 1D array of size n -> O(n) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time quadratic due to substring pairs, space linear due to optimization [OK]

Hint: Nested loops -> O(n²) time; single array -> O(n) space [OK]

Common Mistakes:

• Confusing recursion stack space
• Assuming O(n^3) due to nested loops
• Forgetting space optimization

5. Suppose the regular expression pattern is extended to allow '+' which matches one or more of the preceding element (in addition to '.' and '*'). Which modification to the DP approach correctly handles '+' without increasing time complexity beyond O(m*n)?

hard

A. Modify dp update to require at least one match before repeating for '+', i.e., dp[j] = (prev and match) or (dp[j] and match) but not dp[j - 2] alone, and initialize accordingly

B. Add a separate DP state dimension to track '+' matches explicitly

C. Treat '+' exactly like '*' by copying dp[j] = dp[j] or dp[j - 2] logic

D. Replace '+' with equivalent '.*' in pattern preprocessing

Solution

1. Step 1: Understand '+' semantics

   '+' requires at least one occurrence of preceding element, unlike '*' which allows zero occurrences.

2. Step 2: Adjust DP update logic

   For '+', dp[j] must be true if previous character matched (prev and match) or if repeating the match (dp[j] and match), but not from dp[j - 2] alone which allows zero occurrences.

3. Step 3: Confirm time complexity

   This modification keeps DP table size and iteration unchanged, preserving O(m*n) time complexity.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   '+' requires at least one match, so zero occurrence logic must be excluded [OK]

Hint: '+' differs from '*' by disallowing zero occurrences [OK]

Common Mistakes:

• Treating '+' exactly like '*' allowing zero occurrences