Longest Common Subsequence

Longest Common Subsequence builds a 2-D DP table over two strings, finds the length of their longest shared subsequence, and reconstructs the actual subsequence by tracing the table from bottom-right to top-left.

5 min read Level 4/5 #dsa#dp#lcs

What you'll learn

Write the LCS recurrence for two strings and fill the dp table
Reconstruct the LCS string by backtracking through the filled table
State the time and space complexity and identify real-world applications

The Longest Common Subsequence (LCS) of two strings is the longest sequence of characters that appears in both strings in the same relative order, but not necessarily contiguously. LCS underlies diff tools, version control, and bioinformatics sequence alignment.

State and Recurrence

Let s and t be the two strings of lengths m and n.

State: dp[i][j] = length of LCS of s[0..i-1] and t[0..j-1].

Recurrence:

If s[i-1] === t[j-1]: dp[i][j] = dp[i-1][j-1] + 1
Otherwise: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Base cases: dp[0][j] = 0 and dp[i][0] = 0 for all i, j.

function lcsLength(s, t) {
  const m = s.length, n = t.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 (s[i - 1] === t[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(lcsLength('ABCBDAB', 'BDCAB')); // 4 — "BCAB" or "BDAB"

Time O(mn), space O(mn).

Reconstructing the LCS String

The length alone is often insufficient. To recover the actual subsequence, start at dp[m][n] and backtrack:

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

  // Backtrack to reconstruct
  let i = m, j = n;
  const result = [];
  while (i > 0 && j > 0) {
    if (s[i - 1] === t[j - 1]) {
      result.push(s[i - 1]);
      i--;
      j--;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }
  return result.reverse().join('');
}

console.log(lcs('ABCBDAB', 'BDCAB')); // "BCAB" (one valid LCS)

How the Backtrack Works

At each cell, we follow the path that produced the current value:

If characters matched, both pointers move diagonally and the character is recorded.
Otherwise, move in the direction of the larger neighbor.

When both neighbors are equal, either direction is valid — there may be multiple LCS strings of the same length.

Applications

Domain	Use of LCS
Version control	`git diff` — find unchanged lines
Bioinformatics	DNA/protein sequence alignment
Plagiarism detection	Measure string similarity
Spelling correction	Base metric for edit distance

Up Next

Longest Increasing Subsequence generalizes LCS to a single sequence and introduces an O(n log n) patience-sort solution.

Longest Increasing Subsequence →