Longest Common Subsequence — The Essential Sequence DP Problem for FAANG

Problem Statement#

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence of a string is formed by deleting some characters (possibly none) without changing the relative order of the remaining characters.

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English letters

Example 1:

Input:  text1 = "abcde", text2 = "ace"
Output: 3
Explanation: LCS is "ace" — length 3.

Example 2:

Input:  text1 = "abc", text2 = "abc"
Output: 3
Explanation: LCS is "abc" — the full string.

Example 3:

Input:  text1 = "abc", text2 = "def"
Output: 0
Explanation: No common subsequence exists.

Why This Problem Matters#

Longest Common Subsequence (LCS) is the foundation of sequence DP. It is asked directly at Amazon, Google, Meta, and Microsoft, and it is the building block for Edit Distance, Shortest Common Supersequence, and diff utilities (the diff command used in version control is fundamentally LCS).

The 2D DP table for LCS is one of the most pedagogically important structures in computer science — understanding how to fill it, why the diagonal move represents a character match, and how to reconstruct the subsequence by backtracking teaches you how to think about all sequence alignment problems.

Interviewers specifically ask: "How would you reconstruct the actual LCS, not just the length?" This reconstruction is O(m+n) time once the table is filled, and mastering it directly prepares you for Shortest Common Supersequence (LC 1092) and Edit Distance path reconstruction.

The Core Insight#

Define dp[i][j] as the length of the LCS of text1[:i] and text2[:j] (first i characters of text1, first j characters of text2).

Base cases: dp[0][j] = 0 and dp[i][0] = 0 for all i, j — the LCS of any string with an empty string is 0.

Recurrence:

• If text1[i-1] == text2[j-1] (current characters match): both characters extend the LCS found for the prefixes before them.

  Copy

  dp[i][j] = dp[i-1][j-1] + 1

• If characters do not match: skip one character from either string and take the better result.

  Copy

  dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Answer: dp[m][n] where m = len(text1), n = len(text2).

Intuition: Think of it as two pointers moving through the strings. When characters match, both advance (diagonal move in the table, +1 to LCS). When they do not match, you try skipping one character from either string (left or up in the table).

Building the DP Solution#

Step 1 — Recursive (exponential):

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

Exponential recomputation — each subproblem is solved multiple times.

Step 2 — Top-down with memoization:

from functools import lru_cache
 
def longestCommonSubsequence(text1, text2):
    @lru_cache(None)
    def dp(i, j):
        if i == 0 or j == 0:
            return 0
        if text1[i-1] == text2[j-1]:
            return 1 + dp(i-1, j-1)
        return max(dp(i-1, j), dp(i, j-1))
    return dp(len(text1), len(text2))

O(m * n) time and space. Correct but uses call stack memory.

Step 3 — Bottom-up 2D tabulation:

def longestCommonSubsequence(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] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

Step 4 — Space-optimized 2-row DP: Each row only needs the previous row and the current row. See Optimized Solution below.

Visual Dry Run#

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

DP table (rows = text1, cols = text2, 0-indexed headers show characters):

Selected cell explanations:

• dp[1][1]: text1[0]='a' == text2[0]='a' → dp[0][0]+1 = 1
• dp[3][2]: text1[2]='c' == text2[1]='c' → dp[2][1]+1 = 2
• dp[5][3]: text1[4]='e' == text2[2]='e' → dp[4][2]+1 = 3

Answer: dp[5][3] = 3

Optimized Solution#

Python#

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
 
        # Keep only two rows: prev (i-1) and curr (i)
        prev = [0] * (n + 1)
 
        for i in range(1, m + 1):
            curr = [0] * (n + 1)
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    curr[j] = prev[j - 1] + 1    # diagonal + 1
                else:
                    curr[j] = max(prev[j], curr[j - 1])  # up or left
            prev = curr
 
        return prev[n]

JavaScript#

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

Reconstructing the Actual LCS#

Once the full 2D DP table is filled, backtrack from dp[m][n]:

def reconstruct_lcs(text1, text2, dp):
    i, j = len(text1), len(text2)
    result = []
    while i > 0 and j > 0:
        if text1[i-1] == text2[j-1]:
            result.append(text1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1    # came from above
        else:
            j -= 1    # came from left
    return ''.join(reversed(result))

This reconstructs one valid LCS in O(m+n) time and O(m+n) space for the result.

Complexity Analysis#

Common Mistakes#

1. Confusing subsequence with substring. A subsequence does not need to be contiguous — characters can be skipped. "ace" is a subsequence of "abcde" because you skip "b" and "d". Substring requires contiguity. The recurrence is fundamentally different for substrings (see LC 718).

2. Indexing errors in the 1-indexed DP. The DP table is (m+1) x (n+1) with 1-based indexing. text1[i-1] refers to the i-th character in the 1-indexed scheme. Using text1[i] instead shifts all character accesses by one — a very common off-by-one.

3. Swapping the diagonal and max-skips branches. When characters match, the recurrence uses dp[i-1][j-1] + 1 (diagonal). When they do not match, it uses max(dp[i-1][j], dp[i][j-1]) (up or left). Swapping these branches produces systematically wrong results that can look plausible on small inputs.

4. Confusing the space-optimized approach with 0/1 knapsack direction. In the 2-row LCS approach, the current row is built left-to-right. But prev[j-1] is the diagonal value from the previous row, not the current row. Using curr[j-1] instead of prev[j-1] for the match case gives wrong results.

5. Not initializing the 0th row and column to 0. The base case is that LCS of any string with an empty string is 0. If you forget to initialize the border to 0 (which Python does automatically for list comprehensions, but C++ or Java may not), the table fills incorrectly.

Interview Tips#

• State the DP semantics precisely: "dp[i][j] is the LCS length of the first i characters of text1 and the first j characters of text2."
• Explain both cases aloud: "If characters match, both pointers advance — dp[i-1][j-1] + 1. If not, we try skipping one from either string — max(dp[i-1][j], dp[i][j-1])."
• Offer reconstruction proactively: "Once I have the full 2D table, I can backtrack from dp[m][n] to reconstruct the actual subsequence." This almost always impresses interviewers.
• Mention the rolling-array optimization: "For just the length, I can reduce space to O(n) by keeping only two rows at a time."
• Connect to real-world applications: "LCS is the basis of Unix diff, DNA sequence alignment, and plagiarism detection." This shows breadth.

Follow-up Questions#

Q: How do you reconstruct the actual LCS string? Keep the full 2D table and backtrack from (m, n): when characters match, add to result and move diagonally; otherwise move toward the larger neighbor. Reverse the collected characters.

Q: What is the LCS of three strings? Extend the DP to 3 dimensions: dp[i][j][k] = LCS of text1[:i], text2[:j], text3[:k]. O(m * n * p) time and space. The recurrence has 7 cases instead of 3.

Q: How does LCS relate to Edit Distance? (LC 72) Edit distance counts insertions, deletions, and replacements to convert one string to another. LCS minimizes deletions only (from both strings). edit_distance = (m - LCS) + (n - LCS) when only insertions and deletions are allowed (no replacements) — the Levenshtein variant.

Q: What is the Shortest Common Supersequence length? (LC 1092) SCS length = m + n - LCS(text1, text2). Reconstruction requires tracing the LCS table to interleave non-matching characters.

Q: Can LCS be solved in better than O(m * n)? For general strings, O(m * n) is optimal. For binary strings or small alphabets, the four-Russians method achieves O(m * n / log(m * n)). For practice and interviews, O(m * n) is the expected answer.

Key Takeaways#

• dp[i][j] = dp[i-1][j-1] + 1 when characters match (both pointers advance); dp[i][j] = max(dp[i-1][j], dp[i][j-1]) when they do not (skip one character from either string).
• The DP table dimensions are (m+1) x (n+1) to accommodate the 0th row/column base case (empty prefix).
• Reconstruction from the full table goes from (m, n) back to (0, 0): diagonal on match, toward the larger neighbor on mismatch.
• Rolling 2-row approach reduces space to O(n) for length-only computation; full 2D table is needed for reconstruction.
• LCS is the backbone of Edit Distance, Shortest Common Supersequence, Interleaving String, and diff algorithms — mastering it pays compound returns across all sequence DP problems.
• Asked directly at Amazon, Google, Meta, and Microsoft, and frequently embedded in harder problems at FAANG interviews.