Longest Common Subsequence

Approach Summary

dp[i][j] = LCS of first i chars of s1 and first j chars of s2. If match: dp[i-1][j-1]+1. Else: max(dp[i-1][j], dp[i][j-1]).

Full Solution & Approach

Define dp[i][j] as the length of the longest common subsequence of text1[0..i) and text2[0..j). If text1[i-1] equals text2[j-1], that character extends the LCS, so dp[i][j] = dp[i-1][j-1] + 1. If they differ, the best we can do is skip one of them: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Base cases are the zero row and column — an empty prefix has LCS length 0. Fill the table row by row; the answer is dp[m][n]. The recurrence is the definition of LCS and is the foundation for edit distance and other string DP problems. Space can be reduced to two rolling rows since each cell only reads the current and previous rows, but the full table is the clearest starting point.

Every cell of the m × n table is computed once — O(m × n) time. The full table costs O(m × n) space, reducible to O(min(m, n)) with a rolling row.

Solution Code

Solution

def longest_common_subsequence(text1: str, text2: str) -> int:
    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]

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

public 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];
}

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

Edge Cases to Watch

One string empty — LCS is 0
Identical strings — the LCS is the whole string
No shared characters — 0
Repeated characters — the DP handles counts correctly

How to Recognize This Pattern

LCS of two sequences
2D DP table

Complexity Analysis

Time Complexity

O(m × n)

Space Complexity