jsschools

Longest Common Subsequence (LCS)

Finds the length (and optionally the sequence) of the longest subsequence present in both strings in the same relative order, using a 2D DP table.

Spec ↗

Syntax

lcs(a, b)

Parameters

NameTypeRequiredDescription
a string Yes First string.
b string Yes Second string.

Returns

{ length: number, sequence: string } — Length of the LCS and one such subsequence string.

Examples

function lcs(a, b) {
  const m = a.length, n = b.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 (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]);

  // Backtrack to find the sequence
  let i = m, j = n;
  const seq = [];
  while (i > 0 && j > 0) {
    if (a[i-1] === b[j-1]) { seq.push(a[i-1]); i--; j--; }
    else if (dp[i-1][j] > dp[i][j-1]) i--;
    else j--;
  }
  return { length: dp[m][n], sequence: seq.reverse().join('') };
}

console.log(lcs('AGGTAB', 'GXTXAYB'));
Output 
{ length: 4, sequence: 'GTAB' }

// LCS of two arrays (for diff tools)
function lcsArray(a, b) {
  const m = a.length, n = b.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++)
    dp[i][j] = a[i-1]===b[j-1] ? dp[i-1][j-1]+1 : Math.max(dp[i-1][j],dp[i][j-1]);
  let i=m,j=n; const seq=[];
  while(i>0&&j>0){ if(a[i-1]===b[j-1]){seq.push(a[i-1]);i--;j--;} else dp[i-1][j]>dp[i][j-1]?i--:j--; }
  return seq.reverse();
}

console.log(lcsArray([1,3,4,5,6,7,8],[1,4,5,6,7,8,9]));
Output 
[ 1, 4, 5, 6, 7, 8 ]

Notes

| Case | Time | Space | |---------|-------|-------| | Best | O(mn) | O(mn) | | Average | O(mn) | O(mn) | | Worst | O(mn) | O(mn) | The DP table has m·n entries, each computed in O(1). Space can be reduced to O(min(m,n)) using only two rows if only the length (not the sequence) is needed. LCS is closely related to edit distance (fewer operations needed when LCS is longer) and diff tools (Unix `diff` uses LCS). For very long strings (m,n > 10k), consider Myers' diff algorithm which runs in O(n·d) where d is the edit distance.

See also