Longest Common Subsequence

Problem Statement

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence preserves character order but may skip positions (not contiguous).

Example 1:

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

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0

Constraints:

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

Difficulty: Medium LC: 1143 Round: Technical R1

---

Pattern Recognition

• What is the input structure? Two strings.
• What are we optimizing? Length of the longest sequence of characters appearing in both strings in the same relative order.
• What pattern does this fit? 2D DP on two strings — the canonical LCS.
• Why does this pattern fit? Define dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]. The recurrence is local: match → extend diagonal, mismatch → take max of dropping one character from either string.

---

Approach

Brute Force — Enumerate All Subsequences

For each subsequence of text1, check whether it is a subsequence of text2. Track longest.

Time: O(2^n * m). Space: O(n). Why insufficient: Exponential. For n = 1000, astronomical.

Optimal — 2D DP

Key Insight: dp[i][j] depends only on dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]. If text1[i-1] == text2[j-1], you can extend the common subsequence by 1 (take both). Else, drop one character from either side and take the max.

Transitions:

• 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]).

Base: dp[0][j] = 0, dp[i][0] = 0 (empty string has LCS 0).

Time: O(n * m). Space: O(n * m), reducible to O(min(n, m)).

---

Walkthrough

Trace on text1 = "abcde", text2 = "ace":

n = 5, m = 3.

	""	a	c	e
""	0	0	0	0
a	0	1	1	1
b	0	1	1	1
c	0	1	2	2
d	0	1	2	2
e	0	1	2	3

Cells with matching characters (diagonal +1): (a,a), (c,c), (e,e).

Everywhere else: max of left and top.

Final dp[5][3] = 3. Answer: 3.

---

Implementation

TypeScript

function longestCommonSubsequence(text1: string, text2: string): number {
    const n = text1.length, m = text2.length;
    // dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1].
    const dp: number[][] = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[n][m];
}

C++

#include <string>
#include <vector>
#include <algorithm>

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

Space-optimized version (O(min(n, m)) space):

TypeScript

function longestCommonSubsequenceOptimized(text1: string, text2: string): number {
    // Ensure text2 is the shorter one; we'll use its length for the row.
    if (text1.length < text2.length) [text1, text2] = [text2, text1];
    const n = text1.length, m = text2.length;

    let prev = new Array(m + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        const curr = new Array(m + 1).fill(0);
        for (let j = 1; j <= m; 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[m];
}

C++

int longestCommonSubsequenceOptimized(std::string text1, std::string text2) {
    if (text1.size() < text2.size()) std::swap(text1, text2);
    int n = text1.size(), m = text2.size();
    std::vector<int> prev(m + 1, 0), curr(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (text1[i - 1] == text2[j - 1]) curr[j] = prev[j - 1] + 1;
            else curr[j] = std::max(prev[j], curr[j - 1]);
        }
        std::swap(prev, curr);
    }
    return prev[m];
}

Watch out:

1. Confusing subsequence with substring. Substring is contiguous; subsequence is not.
2. Index offset. text1[i-1] corresponds to dp[i][*].
3. Off-by-one in the rolling-array optimization. The diagonal dependency prev[j-1] is written before you read it in the same row — must use two rows or carefully preserve the value.

---

Complexity Analysis

	Time	Space
Brute Force	O(2^n * m)	O(n)
2D DP	O(n * m)	O(n * m)
Space-Optimized	O(n * m)	O(min(n, m))

Bottleneck: Every cell in the DP table must be filled. Cannot go below O(n * m) without additional structure (like Hunt-Szymanski for sparse matches).

---

Edge Cases

1. Empty string — LCS is 0.
2. Identical strings — LCS is the string length.
3. No common character — LCS is 0.
4. One string is a subsequence of the other — LCS is the shorter string length.
5. Repeated characters — DP handles them; each occurrence can independently match.

---

Related Problems

• LC 1092 — Shortest Common Supersequence — Merge LCS backtrace with the originals.
• LC 72 — Edit Distance — Related 2D DP, different transitions (3 ops instead of 2).
• LC 583 — Delete Operation for Two Strings — Min deletions = n + m - 2 * LCS.
• LC 718 — Maximum Length of Repeated Subarray — Contiguous version (both sides must be substrings).

---

Interview Strategy Notes

Foundational DP problem. 15-20 minutes. Often asked as a warmup before a harder 2D DP like Edit Distance. Interviewer may ask for the actual LCS string (not just length) as a follow-up — be ready to backtrace.

---

What is Expected at Each Level

Junior: Recognizes 2D DP with a hint. Writes the recurrence correctly but may flub indexing.

Mid-level: Writes clean 2D DP. Explains why the recurrence works (match extends diagonal, mismatch drops one side). Discusses space optimization.

Senior: Implements space-optimized version directly. Derives the backtrace for the actual LCS string. Mentions Hunt-Szymanski O((n + r) log n) where r = matching pairs, for sparse-match cases.