Solution

You'll fill a two-dimensional table where each cell answers a smaller version of the same question, and the bottom-right cell falls out as the full answer.

The problem, in plain English

You have two strings. You want the length of the longest run of characters you can find in both, reading left to right, allowed to skip characters but never to reorder them. Think of git diff lining up two versions of a file, or a tool aligning two DNA strands: the shared run is the "spine" both sequences agree on. For "abcde" and "ace", that spine is "ace" — length 3. The characters b and d exist only in the first string, so they're dropped, but what remains still appears in order in both.

The catch is that you cannot just greedily grab matching characters as you scan. When the current two characters disagree, you face a genuine fork: drop a character from the first string, or drop one from the second? Either choice might lead to the better answer, and you can't tell which without looking ahead. That fork is the whole problem.

The mental model

Define a smaller question for every pair of prefixes. Let dp[i][j] be the LCS length of the first i characters of a and the first j characters of b. The answer you want is dp[a.length][b.length] — both strings in full. The empty prefix is the anchor: the LCS of anything with the empty string is 0, so the entire first row and first column are 0. That's why the table has one extra row and one extra column — a border of zeros to lean the first real computations against.

Every inner cell is decided by exactly one comparison: do the two characters this cell stands for — a[i-1] and b[j-1] — match? (The -1 is because row i corresponds to the i-th character, which lives at index i-1 in the zero-indexed string.) There are only two outcomes, and each reads from already-filled neighbours.

A first attempt

Before the table, the natural instinct is recursion: compare the first characters, and recurse on what's left. If they match, that character is part of the answer — count it and move past it in both strings. If they don't, you don't know which one to drop, so try both and keep the better result.

function longestCommonSubsequence(a, b) {
  function helper(i, j) {
    // Ran off the end of either string — no characters left to share.
    if (i === a.length || j === b.length) return 0;

    if (a[i] === b[j]) {
      // Characters match: this pair is in the LCS. Count it, advance both.
      return 1 + helper(i + 1, j + 1);
    }
    // Mismatch: drop a[i], or drop b[j]. Try both, keep the larger.
    return Math.max(helper(i + 1, j), helper(i, j + 1));
  }
  return helper(0, 0);
}

This is correct — it returns the right answer for every input. The problem is speed. On a mismatch the function calls itself twice, and those calls overlap heavily: helper(i+1, j) and helper(i, j+1) both eventually call helper(i+1, j+1), recomputing the entire subproblem from scratch. With two strings of length n that share nothing, the call tree branches at nearly every node, giving roughly O(2^(m+n)) calls. Two 40-character strings would launch billions of redundant calls before returning. The work isn't wrong — it's just done over and over.

The working solution

The fix is to compute each subproblem exactly once and store it. There are only (m+1) × (n+1) distinct (i, j) pairs, so a 2D array holds every answer. Fill it from the top-left corner outward, so every cell's neighbours are ready before the cell needs them.

function longestCommonSubsequence(a, b) {
  const m = a.length;
  const n = b.length;

  // dp[i][j] = LCS length of a's first i chars and b's first j chars.
  // The extra row 0 / column 0 (the empty-prefix border) stay 0.
  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]) {
        // Match: extend the LCS of the two shorter prefixes (the diagonal) by 1.
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        // Mismatch: drop a's char (look up) or b's char (look left); keep the best.
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
}

module.exports = { longestCommonSubsequence };

The two attempts compute the same recurrence; the only change is direction. The recursion works top-down and recomputes; the table works bottom-up and remembers. Each cell is filled once, reading at most three already-known neighbours, so the whole thing runs in O(m × n) time and O(m × n) space — for two 40-character strings, 1681 cells instead of an astronomical recursion tree.

The two branches inside the loop are the heart of it, so look at each on its own.

Match — take the diagonal and add 1. When a[i-1] === b[j-1], this shared character extends whatever LCS the two shorter prefixes already had. "Both prefixes minus this last character" is exactly dp[i-1][j-1], the cell diagonally up-left. Add 1 for the new shared character. We never consult the up or left neighbour on a match: appending a guaranteed-common character can only help, so the diagonal-plus-one is always at least as good as either alternative.

Mismatch — take the max of up and left. When the characters differ, at least one of them is not in the LCS (two different characters can't both be the same shared character). So try dropping each. Dropping a's current character means "the best I can do using a shorter a but all of b" — that's the cell directly above, dp[i-1][j]. Dropping b's character is the cell directly to the left, dp[i][j-1]. Whichever is larger wins. Crucially you do not add 1 here — nothing matched, so no character joins the subsequence.

One line deserves a second look: Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0)). The callback runs once per row, building a fresh array each time. The tempting shorthand new Array(m + 1).fill(new Array(n + 1).fill(0)) is a classic bug — fill puts the same inner array reference in every row, so writing dp[1][1] also changes dp[2][1], dp[3][1], and so on. Each row must be its own array.

Walking through one call

Trace longestCommonSubsequence("AGC", "AC"). Rows are a = "AGC", columns are b = "AC". The border (row 0 and column 0) starts at 0. We fill left to right, top to bottom.

i=1 (a[0]="A"):
  j=1, b[0]="A":  match    → dp[0][0] + 1 = 0 + 1 = 1
  j=2, b[1]="C":  mismatch → max(dp[0][2]=0, dp[1][1]=1) = 1

i=2 (a[1]="G"):
  j=1, b[0]="A":  mismatch → max(dp[1][1]=1, dp[2][0]=0) = 1
  j=2, b[1]="C":  mismatch → max(dp[1][2]=1, dp[2][1]=1) = 1

i=3 (a[2]="C"):
  j=1, b[0]="A":  mismatch → max(dp[2][1]=1, dp[3][0]=0) = 1
  j=2, b[1]="C":  match    → dp[2][1] + 1 = 1 + 1 = 2

The completed table:

        ""   A   C
   ""    0   0   0
   A     0   1   1
   G     0   1   1
   C     0   1   2

Two cells were matches: A at dp[1][1] (giving 1) and C at dp[3][2] (giving 2). Notice the second match read the diagonal dp[2][1] = 1, not the value sitting directly above or to the left. That diagonal is the LCS of "AG" and "A" — the lone A — and the shared C extends it to 2. The bottom-right cell, dp[3][2] = 2, is the answer: the LCS of "AGC" and "AC" is "AC", length 2.

Gotchas

• Subsequence, not substring. This algorithm allows gaps — the matched characters need not be adjacent. If you accidentally reset the count to 0 on every mismatch (the way you would for the longest common substring), you'll get the wrong, smaller answer. LCS carries forward the best-so-far across mismatches via max(up, left); it never resets.
• Off-by-one between the table and the strings. Row i and column j refer to prefix lengths, but the characters they compare live at a[i-1] and b[j-1]. Writing a[i] instead of a[i-1] reads one character too far (and a[m] is undefined), quietly corrupting the answer. The -1 is not optional.
• Adding 1 on a mismatch. The mismatch branch is max(dp[i-1][j], dp[i][j-1]) with no + 1. A stray + 1 there counts characters that never matched, inflating the result. Only the diagonal (match) branch adds 1.
• Taking the max on a match. The symmetric error: writing max(dp[i-1][j], dp[i][j-1]) in the match branch. On a match the diagonal-plus-one is always at least as large as the neighbours, so max happens to give the same number — but it hides the logic and breaks the moment you adapt the code to reconstruct the actual string (where you must follow the diagonal). Match means diagonal, full stop.
• Sharing one inner array across rows. new Array(m + 1).fill(new Array(n + 1).fill(0)) puts the same row reference in every slot, so a write to one row leaks into all of them. Build each row independently with Array.from(..., () => new Array(n + 1).fill(0)).
• Lowercasing the inputs. The problem is case-sensitive: 'A' and 'a' are different characters. Calling .toLowerCase() to "normalise" silently changes the answer ("ABC" vs "abc" should be 0, not 3).

Going further

• Reconstruct the actual subsequence, not just its length. Keep the full dp table, then walk backward from dp[m][n]: when a[i-1] === b[j-1], that character is in the LCS — prepend it and step diagonally to dp[i-1][j-1]; otherwise step toward the larger of the up/left neighbour. The characters you collect, reversed, spell one valid LCS (there can be several of equal length).
• Shrink the space to two rows (or one). Each cell reads only the current and previous row, so you never need the whole grid in memory at once — keep a prev row and a curr row and swap them, dropping space from O(m × n) to O(min(m, n)). The trade-off: you lose the full table, so you can't reconstruct the string afterward (the point above needs all the rows).
• Edit distance is the same table, different recurrence. The Levenshtein edit distance — the fewest single-character insertions, deletions, and substitutions to turn a into b — fills an identically shaped grid. When characters match you copy the diagonal unchanged; when they differ you take 1 + min of the three neighbours (insert, delete, substitute). Recognising LCS as one member of this family of grid-filling string problems is the real payoff.