Longest Common Subsequence

MediumDynamic ProgrammingStringDynamic Programming

Problem

Given two strings, find the length of the longest subsequence that appears in both, keeping each string's original character order but allowing the matching characters to skip over other characters in between.

Example. For "abcde" and "ace", the longest common subsequence is "ace", giving a length of 3.

Key idea

Comparing every subsequence of one string against every subsequence of the other is exponential in both string lengths. The efficient approach instead compares the two strings prefix by prefix, working from the front one character at a time.

If the current characters at the end of each prefix match, that character must belong to some longest common subsequence of the two prefixes, so the answer for these prefixes is one more than the answer for both prefixes with that character removed. If the characters differ, no common subsequence of these two prefixes can end by using both at once, so the best answer is whichever is better between dropping the last character of the first prefix or the last character of the second. Filling a table indexed by how much of each string has been considered, starting from two empty prefixes and working up, means every smaller comparison a cell needs is already solved by the time that cell is reached.

Solution

function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length;
  const n = text2.length;
  const table: number[][] = Array.from({ length: m + 1 }, () => new Array<number>(n + 1).fill(0)); // extra row/col for empty prefixes

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        table[i][j] = table[i - 1][j - 1] + 1; // matching characters extend the shorter prefixes' answer
      } else {
        table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]); // no match: best of dropping either last character
      }
    }
  }

  return table[m][n];
}

Complexity

  • Time: O(m × n). One table cell for every combination of a prefix length from the first string and a prefix length from the second.
  • Space: O(m × n) for the full table; reducible to O(min(m, n)) by keeping only the two most recently computed rows.

Watch out for

  • Row and column zero represent the empty prefix of each string, not its first character, so indices are shifted by one.
  • This measures a subsequence, not a substring; matching characters do not need to be contiguous in either string.
  • The recurrence differs from edit distance on a mismatch: here you take the better of two smaller prefixes, while edit distance also allows a substitution step.

Pattern

This is the two-string prefix-comparison DP pattern: reduce a pair of prefixes to smaller prefixes based on whether their trailing characters match, the same backbone used for edit distance and other string-alignment problems.

Related questions