Solving Longest Common Subsequence in JavaScript: Step-by-Step Guide

Solving Longest Common Subsequence in JavaScript: Step-by-Step Guide

The Longest Common Subsequence (LCS) problem is one of the most classic dynamic programming challenges you will encounter in computer science. Whether you are preparing for technical interviews, building a diff tool, or working on bioinformatics applications, understanding how to solve LCS efficiently is an essential skill. In this guide, we will walk through the problem from its definition to an optimized JavaScript implementation, covering multiple approaches along the way.

What Is the Longest Common Subsequence?

A subsequence is a sequence that appears in the same relative order as the original sequence, but not necessarily contiguously. For example, given the string "ABCDEF", both "ACE" and "BDF" are valid subsequences, while "ACB" is not because the order is violated.

The Longest Common Subsequence of two strings is the longest subsequence that appears in both strings. For instance, given "ABCBDAB" and "BDCABA", one LCS is "BCBA" with a length of 4. Note that there can be multiple valid LCS strings of the same maximum length.

It is important to distinguish LCS from the Longest Common Substring problem. A substring must be contiguous, while a subsequence does not. This distinction changes the algorithm significantly.

Why the LCS Problem Matters

The LCS problem has wide-ranging practical applications across multiple domains:

• Version control systems: Tools like Git use LCS-based algorithms to compute diffs between file versions, showing what was added, deleted, or modified.
• Bioinformatics: DNA and protein sequence alignment relies heavily on LCS variations to find evolutionary relationships between organisms.
• Spell checkers and auto-correction: Comparing a misspelled word against dictionary entries often uses edit distance, which builds on similar dynamic programming principles.
• Plagiarism detection: Finding the longest matching sequences of text between documents helps identify copied content.
• File comparison utilities: Applications like diff and merge tools use LCS to highlight differences between files.

Beyond these direct applications, mastering LCS teaches you the fundamentals of dynamic programming, a problem-solving paradigm that breaks complex problems into overlapping subproblems and stores intermediate results to avoid redundant computation.

Approach 1: Naive Recursion

The most intuitive way to solve LCS is through recursion. We compare characters from the end of both strings. If they match, we include that character and recurse on the remaining prefixes. If they do not match, we take the maximum of two recursive calls: one excluding the last character of the first string, and one excluding the last character of the second string.

function lcsRecursive(str1, str2, m, n) {
  // Base case: if either string is empty, LCS is 0
  if (m === 0 || n === 0) {
    return 0;
  }

  // If last characters match, include this character
  if (str1[m - 1] === str2[n - 1]) {
    return 1 + lcsRecursive(str1, str2, m - 1, n - 1);
  }

  // Otherwise, take the maximum of excluding one character
  return Math.max(
    lcsRecursive(str1, str2, m - 1, n),
    lcsRecursive(str1, str2, m, n - 1)
  );
}

const str1 = "ABCBDAB";
const str2 = "BDCABA";
console.log(lcsRecursive(str1, str2, str1.length, str2.length)); // Output: 4

While this approach is correct, it suffers from a major performance issue. The time complexity is O(2^(m+n)) in the worst case because each call branches into two more calls, and many subproblems are solved repeatedly. For strings longer than about 20 characters, this becomes impractical.

Approach 2: Memoization (Top-Down Dynamic Programming)

The recursive solution recomputes the same subproblems many times. We can fix this by storing results in a cache, a technique called memoization. Before making a recursive call, we check whether we have already computed the answer for that particular pair of indices.

function lcsMemoized(str1, str2) {
  const m = str1.length;
  const n = str2.length;

  // Create a memo table initialized with -1
  const memo = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(-1)
  );

  function solve(i, j) {
    // Base case
    if (i === 0 || j === 0) {
      return 0;
    }

    // Return cached result if available
    if (memo[i][j] !== -1) {
      return memo[i][j];
    }

    // If characters match
    if (str1[i - 1] === str2[j - 1]) {
      memo[i][j] = 1 + solve(i - 1, j - 1);
    } else {
      memo[i][j] = Math.max(solve(i - 1, j), solve(i, j - 1));
    }

    return memo[i][j];
  }

  return solve(m, n);
}

console.log(lcsMemoized("ABCBDAB", "BDCABA")); // Output: 4

With memoization, each unique pair of indices is computed only once. The time complexity drops to O(m * n), and the space complexity is also O(m * n) for the memo table plus the recursion stack. This makes the solution practical for much larger inputs.

Approach 3: Bottom-Up Dynamic Programming (Tabulation)

The bottom-up approach eliminates recursion entirely by building a table iteratively. We create a 2D array dp where dp[i][j] represents the length of the LCS of the first i characters of str1 and the first j characters of str2. We fill this table row by row, left to right.

function lcsTabulation(str1, str2) {
  const m = str1.length;
  const n = str2.length;

  // Create a (m+1) x (n+1) table initialized to 0
  const dp = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(0)
  );

  // Build the table bottom-up
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        // Characters match: extend the LCS
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        // Characters don't match: take the best of two options
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
}

console.log(lcsTabulation("ABCBDAB", "BDCABA")); // Output: 4

This approach has the same O(m * n) time and space complexity as memoization, but it avoids the overhead of recursive function calls and potential stack overflow for very large inputs. It is generally the preferred approach in production code.

Reconstructing the Actual Subsequence

So far, we have only computed the length of the LCS. In many real-world applications, you need the actual subsequence string itself. We can reconstruct it by backtracking through the DP table we built in the tabulation approach.

function lcsWithString(str1, str2) {
  const m = str1.length;
  const n = str2.length;

  const dp = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(0)
  );

  // Build the DP table
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[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 actual LCS string
  let i = m;
  let j = n;
  let lcs = "";

  while (i > 0 && j > 0) {
    if (str1[i - 1] === str2[j - 1]) {
      // Characters match: this character is part of the LCS
      lcs = str1[i - 1] + lcs;
      i--;
      j--;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
      // Move in the direction of the larger value
      i--;
    } else {
      j--;
    }
  }

  return {
    length: dp[m][n],
    subsequence: lcs
  };
}

const result = lcsWithString("ABCBDAB", "BDCABA");
console.log(result.length);       // Output: 4
console.log(result.subsequence);  // Output: "BCBA"

The backtracking process starts from dp[m][n] and works backwards. When characters match, they are part of the LCS. When they do not, we move in the direction of the larger adjacent value. This reconstruction adds O(m + n) time complexity, which is negligible compared to the table construction.

Space Optimization

If you only need the length of the LCS and not the actual string, you can reduce the space complexity from O(m * n) to O(min(m, n)). This is because each row in the DP table only depends on the previous row. By keeping just two rows in memory and swapping them, we save significant space.

function lcsSpaceOptimized(str1, str2) {
  // Ensure str2 is the shorter string for minimal space usage
  if (str1.length < str2.length) {
    [str1, str2] = [str2, str1];
  }

  const m = str1.length;
  const n = str2.length;

  let previous = new Array(n + 1).fill(0);
  let current = new Array(n + 1).fill(0);

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        current[j] = previous[j - 1] + 1;
      } else {
        current[j] = Math.max(previous[j], current[j - 1]);
      }
    }
    // Swap rows
    [previous, current] = [current, previous];
    // Reset current row for next iteration
    current.fill(0);
  }

  return previous[n];
}

console.log(lcsSpaceOptimized("ABCBDAB", "BDCABA")); // Output: 4

This optimization is particularly valuable when dealing with very long strings where the full O(m * n) table would consume too much memory. However, note that with this approach, you can no longer backtrack to reconstruct the actual subsequence since you do not retain the full table.

Best Practices

When implementing LCS in JavaScript, keep the following best practices in mind:

• Choose the right approach for your use case: Use tabulation for production code, memoization when you want a quick transformation of a recursive solution, and space-optimized tabulation when memory is constrained and you only need the length.
• Validate inputs: Always check for empty strings, null, or undefined values before processing. Defensive programming prevents runtime errors.
• Consider string length limits: For extremely long strings, even O(m * n) time may be too slow. In such cases, consider heuristic approaches or the Hunt-Szymanski algorithm, which performs better when the number of matching character pairs is small.
• Use typed arrays for performance: When working with very large DP tables, consider using Int32Array instead of regular JavaScript arrays for better memory efficiency and speed.
• Handle Unicode correctly: JavaScript strings are UTF-16, and some characters (like emoji) are represented by surrogate pairs. If your input may contain such characters, consider using Array.from(str) to split strings into individual code points before processing.
• Write tests: Test edge cases including empty strings, identical strings, completely different strings, single-character strings, and strings with repeated characters.

Here is an example of a robust, production-ready LCS function that incorporates input validation and Unicode handling:

function longestCommonSubsequence(str1, str2) {
  // Input validation
  if (typeof str1 !== "string" || typeof str2 !== "string") {
    throw new TypeError("Both inputs must be strings");
  }

  // Handle Unicode by converting to arrays of code points
  const arr1 = Array.from(str1);
  const arr2 = Array.from(str2);
  const m = arr1.length;
  const n = arr2.length;

  if (m === 0 || n === 0) {
    return { length: 0, subsequence: "" };
  }

  const dp = Array.from({ length: m + 1 }, () =>
    new Int32Array(n + 1)
  );

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (arr1[i - 1] === arr2[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 subsequence
  let i = m, j = n;
  const lcsChars = [];

  while (i > 0 && j > 0) {
    if (arr1[i - 1] === arr2[j - 1]) {
      lcsChars.unshift(arr1[i - 1]);
      i--;
      j--;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }

  return {
    length: dp[m][n],
    subsequence: lcsChars.join("")
  };
}

// Example usage
console.log(longestCommonSubsequence("ABCBDAB", "BDCABA"));
// Output: { length: 4, subsequence: "BCBA" }

console.log(longestCommonSubsequence("AGGTAB", "GXTXAYB"));
// Output: { length: 4, subsequence: "GTAB" }

Conclusion

The Longest Common Subsequence problem is a foundational algorithm that every developer should understand. Starting from a naive recursive approach, we progressively optimized the solution using memoization, bottom-up tabulation, and space optimization techniques. Each approach trades off simplicity, performance, and memory usage differently, and the right choice depends on your specific requirements. By mastering LCS, you not only gain a practical tool for building diff tools, sequence aligners, and comparison utilities, but you also develop a deeper intuition for dynamic programming that will serve you across countless other algorithmic challenges. Practice implementing these solutions from scratch, test them against edge cases, and you will be well prepared to tackle LCS and its many variations in both interviews and real-world projects.