How do you solve the longest common subsequence problem?

A subsequence keeps order but does not require contiguity. The two-dimensional state is the pair of prefixes. If the last characters match, they can be part of the answer. If they do not, at least one of them cannot be in the optimal pair, so take the better of dropping either.

function longestCommonSubsequence(a, b) {
  const rows = a.length + 1;
  const cols = b.length + 1;
  const dp = Array.from({ length: rows }, () => new Array(cols).fill(0));
  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      if (a[i - 1] === b[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[a.length][b.length];
}

Reading the table

• A match moves diagonally and adds one
• A mismatch moves up or left, keeping the larger value
• The answer is in the bottom-right cell
• The table uses O(n * m) time and space
• Only the previous row is needed if you only want the length

To reconstruct the actual subsequence, walk backwards from the bottom-right cell. On a match, prepend the character and move diagonally. Otherwise move toward the larger neighbouring cell. That produces one valid LCS, not necessarily the only one.