snippetjavascriptTip

How can I find the longest common subsequence of two strings in JavaScript?

Submitted by: @import:30-seconds-of-code·Mar 2, 2026·

Viewed 0 times

longestjavascriptsubsequencetwohowfindcommonstringsthecan

Problem

The longest common subsequence (LCS) is the longest subsequence common to all given sequences. It is not the same as the longest common substring, which must occupy consecutive positions within the original sequences. The LCS problem can be easily solved using <dfn title='A problem-solving method that breaks down a complex problem into smaller, manageable parts, solves each part, and then optimizes those solutions to find the best overall answer.'>dynamic programming</dfn>.
> [!NOTE]
>
> Solving this problem with dynamic programming is not the most efficient way to find the LCS. However, dynamic programming is the most straightforward way to understand the problem. If you're looking for a more efficient solution, you can search for it online.
Before we jump into the code, let's look at an example to understand the problem better. Consider the following two strings:

Solution

const string1 = 'AGGTAB';
const string2 = 'GXTXAYB';

>
> Solving this problem with dynamic programming is not the most efficient way to find the LCS. However, dynamic programming is the most straightforward way to understand the problem. If you're looking for a more efficient solution, you can search for it online.
Before we jump into the code, let's look at an example to understand the problem better. Consider the following two strings:
The longest common subsequence of these two strings is 'GTAB', which has a length of 4. _But how did we arrive to this conclusion?_ What is trivial for human intuition may not be so for computer code. This is where dynamic programming comes into play.
Instead of trying to solve the problem directly, we can break it down into smaller subproblems. We can create a 2D table to store the lengths of the longest common subsequences of the prefixes of the two strings. Then, using the values in this table, we can build up the solution to the original problem.
Here's a step-by-step guide to finding the LCS of these two strings using this approach. Use the buttons below the table to replay each step and move forward or backward.

Code Snippets

const string1 = 'AGGTAB';
const string2 = 'GXTXAYB';

const longestCommonSubsequence = (a, b) => {
  // Find the lengths of the two sequences
  const m = a.length, n = b.length;

  // Create a 2D array to store lengths
  const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));

  // Fill the 2D array
  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]);
      }
    }
  }

  // Reconstruct the LCS
  let i = m, j = n, lcs = [];

  while (i > 0 && j > 0) {
    if (a[i - 1] === b[j - 1]) {
      lcs.unshift(a[i - 1]);
      i--;
      j--;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }

  if (typeof a === 'string' && typeof b === 'string')
    return lcs.join('');

  return lcs;
}

longestCommonSubsequence(
  'AGGTAB',
  'GXTXAYB'
); // 'GTAB'

longestCommonSubsequence(
  ['A','B','C','B','A'],
  ['C', 'B', 'A', 'B', 'A', 'C']
); // ['C', 'B', 'A']

Context

From 30-seconds-of-code: longest-common-subsequence

Revisions (0)

No revisions yet.