Longest Common Subsequence

The Longest Common Subsequence (LCS) problem asks: given two strings, what is the longest sequence of characters that appears in both strings in the same order, but not necessarily consecutively?

For example, the LCS of "ABCBDAB" and "BDCAB" is "BCAB" — length 4. The characters do not have to be next to each other, they just have to appear in the same relative order in both strings.

The DP Table Approach

We build a 2D table where dp[i][j] stores the length of the LCS of the first i characters of string 1 and the first j characters of string 2. If the characters match, we extend the previous LCS by 1. If they do not, we take the best of skipping a character from either string.

function lcs(s1, s2) {
  const m = s1.length;
  const n = s2.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 (s1[i - 1] === s2[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];
}

console.log(lcs("ABCBDAB", "BDCAB"));
console.log(lcs("AGGTAB", "GXTXAYB"));

Time Complexity

The time complexity is O(m × n) where m and n are the lengths of the two strings. Space is also O(m × n) for the table. Since every cell in the table is filled once, and each fill takes constant time, this is quite efficient for strings up to a few thousand characters.

You can optimize space to O(min(m, n)) by only keeping two rows of the table at a time, since each row only depends on the previous one.

Real World Applications

LCS shows up in surprising places. Diff tools that compare files and show what changed use LCS to find the longest unchanged sections. Bioinformatics tools align DNA sequences using variations of LCS to find similar regions between organisms.

It also appears in version control systems (git diff), plagiarism detection, and even in spell checkers that suggest corrections by comparing your word against a dictionary. Any time you need to measure how similar two sequences are, LCS is a good starting point.