Free lesson · DSA Mastery - Interview Prep, End to End

Longest Common Subsequence

Hard9 min readdsadynamic-programming

Longest Common Subsequence

Longest Common Subsequence (LCS) is the canonical two-string alignment DP and one of the most foundational string DPs: given two strings, find the length of the longest subsequence common to both. The DP is dp[i][j] = dp[i-1][j-1] + 1 if s[i-1] == t[j-1], else max(dp[i-1][j], dp[i][j-1]) - the textbook "match: extend diagonal" / "differ: drop one side" pattern that recurs across the sub-group. It establishes the 2-D alignment state, the character-comparison branching, and the row-by-row fill order on the simplest possible substrate where the semantics are completely transparent. We present the 2-D DP (canonical) and the 1-D space-optimized version (optimal).

The insight: consider the last characters of the two strings. Case 1: s[m-1] == t[n-1]. Then this matching pair must be part of some LCS (we lose nothing by including it), so lcs(s, t) = 1 + lcs(s[0..m-2], t[0..n-2]). Case 2: s[m-1] != t[n-1]. Then the LCS doesn't include both last characters; it either skips s[m-1] or skips t[n-1]. Try both: lcs(s, t) = max(lcs(s[0..m-2], t), lcs(s, t[0..n-2])). This decomposition gives the DP directly.

The Problem

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 a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

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

Explanation: The longest common subsequence is "ace" and its length is 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; consist of lowercase English characters.

Approaches Overview

#	Approach	Time	Space	Verdict
1	2-D alignment DP	O(m · n)	O(m · n)	Canonical
2	1-D space-optimized (single row + diagonal)	O(m · n)	O(min(m, n))	Optimal

dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]. Base: dp[0][j] = dp[i][0] = 0 (empty prefix has 0 LCS). Transition: 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]). Answer: dp[m][n]. The 1-D optimization carries a single row plus a "previous diagonal" variable to retain dp[i-1][j-1] after dp[j] is updated.

Approach 1: 2-D Alignment DP - Canonical

The Idea

The DP state is (prefix of text1, prefix of text2). The base case is "either prefix empty → LCS is 0." For interior cells, branch on character comparison: matching characters extend the LCS via the diagonal predecessor; non-matching characters force a choice (drop one string's last character).

Logic Flowchart

graph TD
    A["dp[0][j] = 0, dp[i][0] = 0 (empty prefix)"] --> B["for each interior (i, j):"]
    B --> C{"text1[i-1] == text2[j-1]?"}
    C -->|Yes| D["dp[i][j] = dp[i-1][j-1] + 1"]
    C -->|No| E["dp[i][j] = max(dp[i-1][j], dp[i][j-1])"]
    D --> B
    E --> B
    B --> F["return dp[m][n]"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows LCS: empty-prefix boundaries are zero, and each interior cell either extends the diagonal predecessor by one on a character match or takes the max of its upper and left neighbors on a mismatch, returning the value at the full lengths.

Code

public static int longestCommonSubsequence(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] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

// Usage:
// longestCommonSubsequence("abcde", "ace") -> 3
// longestCommonSubsequence("abc", "abc") -> 3
// longestCommonSubsequence("abc", "def") -> 0

This Java code finds the longest common subsequence with a 2-D DP indexed by prefix lengths, branching on character match versus mismatch.

Step-by-Step Walkthrough

Tracing longestCommonSubsequence("abcde", "ace"):

graph LR
    F0["dp[1][1]: 'a'='a' → dp[0][0]+1 = 1; row 1 = [0,1,1,1]"]
    F1["row 2 ('b'): 'b'≠'a', 'b'≠'c', 'b'≠'e' → row 2 = [0,1,1,1] (carries)"]
    F2["row 3 ('c'): 'c'='c' at j=2 → dp[2][1]+1=2; row 3 = [0,1,2,2]"]
    F3["row 4 ('d'): no matches → [0,1,2,2]; row 5 ('e'): 'e'='e' at j=3 → dp[4][2]+1=3 → dp[5][3]=3"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough finds the LCS of abcde and ace: the dp grows along three matching characters a, c, e, ending with three at the bottom-right.

Result: 3.

Complexity

Time: O(m · n) - one pass over the table. Space: O(m · n) for the table.

Approach 2: 1-D Space-Optimized - Optimal

The Idea

Each row reads only from the previous row and the current row's left neighbor. Carry one row dp[] of size n + 1, updated left-to-right. The complication: when text1[i-1] == text2[j-1], we need dp[i-1][j-1] - the previous row's value at index j - 1, which has already been overwritten by this row's dp[j-1] value. Workaround: save dp[j-1]'s old value in a prevDiag variable before updating dp[j].

Code

public static int longestCommonSubsequenceOptimized(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    if (m < n) return longestCommonSubsequenceOptimized(text2, text1);    // ensure n <= m for smaller dp
    int[] dp = new int[n + 1];
    for (int i = 1; i <= m; i++) {
        int prevDiag = 0;                                                  // = old dp[0] = 0
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];                                              // save current dp[j] (= old upper neighbor)
            if (text1.charAt(i - 1) == text2.charAt(j - 1))
                dp[j] = prevDiag + 1;
            else
                dp[j] = Math.max(dp[j], dp[j - 1]);                        // max(upper, left)
            prevDiag = temp;                                               // becomes the diagonal for next j
        }
    }
    return dp[n];
}

// Usage: longestCommonSubsequenceOptimized("abcde", "ace") -> 3

This Java code computes LCS with a single 1-D array plus a previous-diagonal variable, updated left-to-right to preserve the diagonal predecessor reads.

Complexity

Time: O(m · n). Space: O(min(m, n)).

Complexity Comparison

Approach	Time	Space	Key Idea
2-D DP	O(m · n)	O(m · n)	dp[i][j] over prefix lengths; branch on match
1-D space-optimized	O(m · n)	O(min(m, n))	single row + prevDiag variable for diagonal read

Both compute the same length; the 1-D version saves space by retaining only the diagonal predecessor via an extra variable. The structural lesson is the two-string alignment skeleton with character-comparison branching - the foundational template the entire String DP sub-group builds on.

Variations & Follow-ups

How does the "match: diagonal / differ: max of two neighbors" pattern generalize?

LCS's transition pattern - when characters match, extend the diagonal predecessor; when they differ, take the max of the upper and left neighbors - is the canonical two-string alignment pattern. Variations across the sub-group use the same skeleton with different operations:

Edit Distance: match → dp[i-1][j-1] (no edit), differ → 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) (replace/delete/insert).
Distinct Subsequences: match → dp[i-1][j-1] + dp[i-1][j], differ → dp[i-1][j].
Interleaving String: match either side → OR of the corresponding predecessor.
Shortest Common Supersequence: match → dp[i-1][j-1] + 1, differ → min(dp[i-1][j], dp[i][j-1]) + 1.

The skeleton is the same (dp[i][j] over prefix lengths, three-neighbor reads); the what to do per case changes per problem. The general principle: two-string alignment DPs are a family with shared structure. Recognizing the family - and matching the per-case operations to the problem's semantics - is the design step. LCS is the cleanest first instance, with operations as simple as possible.

Why does the matching case use the diagonal predecessor?

When s[i-1] == t[j-1], the matching pair can be part of the LCS. Including it means we use up the last character of both prefixes, leaving sub-prefixes of lengths i - 1 and j - 1 - that's dp[i-1][j-1]. Including the match is always at least as good as not: if some LCS doesn't include this match, we could append the match to it (potentially overlapping with characters used inside, but at least it doesn't hurt the count). So the recurrence is dp[i][j] = dp[i-1][j-1] + 1 directly, without considering "skip the match." Subtle but worth proving carefully: a more cautious formulation would also include max(dp[i-1][j], dp[i][j-1]) in the match case. But it can be shown those values are ≤ dp[i-1][j-1] + 1, so the match diagonal always dominates. So the simpler form is correct. The general lesson: when a transition has multiple branches, sometimes one branch dominates others under a condition, simplifying the recurrence. Recognizing dominance saves work and clarifies the DP's logic.

How is LCS related to other string-distance metrics?

LCS is one of several edit-distance-like metrics:

LCS measures the longest common subsequence - equivalent to "minimum deletions needed to make s and t equal" (where deletions are the only allowed edit). The Min Deletions to Make Equal problem is m + n - 2 · LCS(s, t).
Edit Distance (next topic) allows insertions, deletions, and replacements; the metric is "minimum operations to transform s into t."
Hamming distance counts position-wise mismatches (only for equal-length strings).

LCS and Edit Distance share the same DP table shape and skeleton, with different operations. The relationship: LCS is a special case where only deletions count; Edit Distance is the full version. Their DP recurrences mirror each other structurally. After this topic and the next, you should see them as siblings of the same family - one optimization (LCS = max matches), one optimization with broader edit operations (Edit Distance = min operations).

What about path reconstruction (recovering the LCS string)?

The DP gives the length of the LCS; to recover the actual subsequence, backtrack from dp[m][n]:

If text1[i-1] == text2[j-1], this character is part of the LCS; prepend it and move to (i-1, j-1).
Otherwise, move to whichever of (i-1, j) or (i, j-1) has the larger dp value (in case of a tie, either works).
Stop when i = 0 or j = 0.

The collected characters in reverse give one valid LCS. The 1-D space-optimized version cannot reconstruct the LCS - it discards the table. Trade-off: if the problem asks for the length only, use the 1-D version (saves space); if the LCS itself is needed, use the 2-D version (preserves history). This trade-off recurs throughout DP: space-optimized versions are leaner but lose reconstruction history.

What about edge cases?

One empty string: LCS is 0.
Identical strings: LCS is m = n.
No common characters: LCS is 0.
One string is a subsequence of the other: LCS equals the shorter string's length.
Maximum size (1000 × 1000): O(m · n) = 10⁶ - trivially fast.

Common Interview Pitfalls

Confusing subsequence with substring. Subsequence allows non-contiguous matches; substring requires contiguity. LCS is for subsequences.
Off-by-one in indices. text1[i-1] is the character at the end of the i-prefix; text1.charAt(i) would be wrong.
Including max(neighbors) in the match branch unnecessarily. The diagonal +1 always dominates on a match; including extra terms is correct but wasteful.
In-place 1-D update without diagonal preservation. The prevDiag variable is essential when matching; without it, the diagonal predecessor read is corrupted.

Why This Topic Matters

Longest Common Subsequence is the canonical two-string alignment DP - dp[i][j] over prefix lengths, with the "match: extend diagonal" / "differ: max of two neighbors" branching pattern. It establishes the 2-D alignment state, the character-comparison branching, the row-by-row fill order, and the 1-D space optimization with diagonal preservation. The skeleton is reused (with different operations per case) across the sub-group's two-string problems: Edit Distance, Distinct Subsequences, Interleaving String, Wildcard Matching, Regex Matching, Shortest Common Supersequence. LCS is the cleanest first instance.

The next topic, Edit Distance, generalizes LCS to the minimum operations metric: given two strings, find the minimum number of insertions, deletions, and replacements (each costing 1) to transform word1 into word2. The DP is dp[i][j] = dp[i-1][j-1] if characters match (no edit needed) else 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) (replace, delete, insert). It's the classical edit-distance DP - used in spell checkers, DNA-sequence comparison, version-control diffs - and extends the LCS pattern to the full set of single-character edits.

Back to DSA Mastery - Interview Prep, End to End