Longest Common Subsequence — The 2D DP Template You Will Reuse Forever

Problem Statement#

Given two strings text1 and text2, return the length of their longest common subsequence. If no common subsequence exists, return 0.

A subsequence of a string is a new string generated by deleting some characters (possibly none) without changing the relative order of the remaining characters. A common subsequence is one that appears in both strings.

Example: text1 = "abcde", text2 = "ace" returns 3. The longest common subsequence is "ace".

Example: text1 = "abc", text2 = "def" returns 0.

Constraints: 1 is less than or equal to text1.length, text2.length is less than or equal to 1000. That allows an O(m * n) DP — exactly the budget we will use.

Why This Problem Matters#

Longest Common Subsequence (LCS) is arguably the single most important DP template you will encounter. Amazon, Google, Microsoft, Adobe, and Bloomberg ask it because it is the parent recurrence behind a long list of interview favorites: Edit Distance, Delete Operation for Two Strings, Shortest Common Supersequence, Distinct Subsequences, and even Longest Palindromic Subsequence (which is LCS(s, reverse(s))).

Outside of interviews, LCS powers git diff, rsync, bioinformatics sequence alignment, and merge tooling. Mastering it pays dividends far beyond LeetCode.

The Core Insight (Recurrence)#

Define dp[i][j] as the length of the longest common subsequence of text1[0..i) and text2[0..j). The recurrence has two cases:

• If text1[i-1] == text2[j-1]: the matching characters can both contribute. dp[i][j] = dp[i-1][j-1] + 1.
• Otherwise we drop one character from one string. dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Base cases: dp[0][j] = 0 and dp[i][0] = 0 (empty string has no common subsequence).

Optimal substructure holds because the LCS of two strings either uses their last characters together (when matched) or excludes one — there is no third option.

Building the DP Solution (Recursion to Memo to Tabulation)#

Top-down: solve(i, j) returns the LCS length of the prefixes text1[0..i) and text2[0..j). Base case is i == 0 or j == 0 returning 0. Recurse on the matching or non-matching branch. Memoize on (i, j) for O(m * n) time and O(m * n) memory plus stack.

Tabulation 2D: allocate dp[m + 1][n + 1] initialized to 0, fill row by row. This is the canonical version interviewers expect.

Tabulation 1D: each dp[i][j] only reads dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]. Keep two rolling arrays of length min(m, n) + 1. Iterate the shorter dimension as the inner loop to minimize memory.

For very long strings where m or n approach 10^5, Hunt-Szymanski runs in O((r + n) log n) where r is the number of matching pairs — a niche interview answer reserved for very specific follow-ups.

Visual Dry Run (DP Table Trace)#

Trace text1 = "abcde", text2 = "ace". The table has 6 rows and 4 columns (indices 0..m and 0..n).

         ""  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

Walking through:

• dp[1][1]: a == a, so dp[0][0] + 1 = 1.
• dp[1][2]: a vs c, so max(dp[0][2], dp[1][1]) = max(0, 1) = 1.
• dp[3][2]: c == c, so dp[2][1] + 1 = 2.
• dp[5][3]: e == e, so dp[4][2] + 1 = 3.

Final answer: dp[5][3] = 3, matching "ace".

Optimized Solution — Space-Optimized Python and JavaScript#

Python — 1D Rolling Array#

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # Make text2 the shorter one for memory efficiency.
        if len(text2) > len(text1):
            text1, text2 = text2, text1
        m, n = len(text1), len(text2)
        prev = [0] * (n + 1)
        curr = [0] * (n + 1)
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    curr[j] = prev[j - 1] + 1
                else:
                    curr[j] = max(prev[j], curr[j - 1])
            prev, curr = curr, prev
            for k in range(n + 1):
                curr[k] = 0
        return prev[n]

JavaScript — 1D Rolling Array#

var longestCommonSubsequence = function (text1, text2) {
  if (text2.length > text1.length) {
    [text1, text2] = [text2, text1];
  }
  const m = text1.length;
  const n = text2.length;
  let prev = new Array(n + 1).fill(0);
  let curr = new Array(n + 1).fill(0);
  for (let i = 1; i <= m; i += 1) {
    for (let j = 1; j <= n; j += 1) {
      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] = [curr, prev];
    curr.fill(0);
  }
  return prev[n];
};

Complexity Analysis#

• Time: O(m * n). Each cell computes in O(1) and we touch every cell.
• Space: O(m * n) for the textbook 2D tabulation, O(min(m, n)) for the rolling-row optimization, O(m * n) plus stack for memoization.
• Hunt-Szymanski achieves O((r + n) log n) where r is the number of character-match pairs — useful when one string is much sparser, but rarely required in interviews.

Common Mistakes#

• Confusing subsequence with substring. Substring requires contiguity and uses a different recurrence (Longest Common Substring resets to 0 on mismatches).
• Mixing up 1-based and 0-based indexing. The standard convention is dp[i][j] for text1[0..i) so the prefix is exclusive on the right; the character compared is text1[i-1]. Stick to one convention.
• Reading from curr when you should read from prev. In the rolling optimization, dp[i-1][j-1] lives in prev[j-1] while dp[i][j-1] lives in curr[j-1]. Swapping these breaks the answer.
• Returning the LCS itself when only the length was asked. Reconstruction is a follow-up; do not over-deliver under time pressure.
• Allocating O(m * n) characters to reconstruct. That is fine for correctness but wasteful if only length is needed.

Interview Tips#

• Open with the recurrence and a 4x4 hand-traced table. That earns credit before code is written.
• Mention the LPS = LCS(s, reverse(s)) connection if Longest Palindromic Subsequence has come up — it shows breadth.
• For senior loops, mention Edit Distance and Shortest Common Supersequence as direct cousins. Both share the same shape with different transitions.
• Ask whether the interviewer wants the length only or the actual subsequence. Reconstruction adds O(m + n) work but doubles the code length.

Follow-up Questions#

• Reconstruct the LCS string, not just its length. Walk the 2D table backwards from dp[m][n].
• Print all distinct LCS strings. That is a recursive enumeration on the DP table; exponential in worst case.
• Edit Distance / Levenshtein distance. Same shape, transitions are insert / delete / replace.
• Longest Common Substring. Reset to 0 on mismatch; track a global maximum.
• Print the diff between two strings (insertions and deletions). LCS is the foundation of git diff.

Key Takeaways#

• Longest Common Subsequence is the canonical 2D DP on two strings: state, transition, and base case all fit in three lines.
• Time is O(m * n); space drops to O(min(m, n)) with rolling rows — interviewers love this optimization.
• The recurrence captures the fundamental "match or skip" decision that powers Edit Distance, Shortest Common Supersequence, Longest Palindromic Subsequence, and many more.
• Memoization, tabulation, and 1D-rolling tabulation are all valid; tabulation with rolling rows is the strongest single-shot interview answer.
• LCS is the algorithmic backbone of diff utilities and version control — appreciating that connection often impresses interviewers.
• Memorize the four-character template: equal characters add one to the diagonal; otherwise take the max of left and up.