Longest Common Subsequence Algorithm

Given two strings, find the longest sequence of characters that appears in both — in the same order, but not necessarily next to each other.

This isn't the same as "longest common substring." A subsequence can skip characters. "ACE" is a subsequence of "ABCDE."

This problem powers real tools: diff algorithms, DNA sequence alignment, plagiarism detection, version control systems.

The intuition

Build a 2D table. Rows represent characters of string 1. Columns represent characters of string 2.

At each cell (i, j), ask: do the characters match? If yes, the LCS length is 1 + whatever we had at (i-1, j-1). If no, take the better result from either skipping a character in string 1 or string 2.

The code

function longestCommonSubsequence(str1, str2) {
    const m = str1.length;
    const n = str2.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 (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]);
            }
        }
    }

    return dp[m][n];
}

Complexity

• Time: O(m * n) — fill every cell in the table.
• Space: O(m * n) — the 2D table. Can be reduced to O(min(m, n)) with row optimization.

Trade-offs

DP gives you the exact answer efficiently. But for very long strings (think genome sequences with millions of characters), even O(m * n) space can be a problem. In those cases, Hirschberg's algorithm computes LCS in O(min(m, n)) space while keeping the same time complexity.