🚀 Supercharge Your Career — Explore Preparation tools like Free AI Mock Interviews, Job Tracker, Resume & Cover Letter Builder, and much more!
Data Structure and Algorithm
Algorithms
Dynamic Programming
Longest Common Subsequence

Longest Common Subsequence (LCS)

Given two sequences, find the length of the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but is not necessarily contiguous.

Examples

Example 1

  • Sequence X: "ABCDGH" (length 6)
  • Sequence Y: "AEDFHR" (length 6)
  • LCS: "ADH" (length 3)

Example 2

  • Sequence X: "AGGTAB" (length 6)
  • Sequence Y: "GXTXAYB" (length 7)
  • LCS: "GTAB" (length 4)

Mathematical Substructure

Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. Let L(m, n) be the length of LCS of these two sequences.

  1. If last characters match (X[m-1] === Y[n-1]): L(m, n) = 1 + L(m-1, n-1)
  2. If last characters do not match (X[m-1] !== Y[n-1]): L(m, n) = max(L(m-1, n), L(m, n-1))

1. Recursive Implementation (Naive)

This naive recursive approach has a worst-case time complexity of O(2^(m+n)) because it solves the same subproblems repeatedly.

function lcsRecursive(X, Y, m, n) {
    // Base Case
    if (m === 0 || n === 0) return 0;
 
    // If last characters match, they are part of LCS
    if (X[m - 1] === Y[n - 1]) {
        return 1 + lcsRecursive(X, Y, m - 1, n - 1);
    } 
    // If last characters do not match, take maximum of two choices
    else {
        return Math.max(
            lcsRecursive(X, Y, m - 1, n),
            lcsRecursive(X, Y, m, n - 1)
        );
    }
}

2. Memoization Implementation (Top-Down DP)

To avoid redundant computations, we store the results of subproblems in a 2D lookup table.

function lcsMemoization(X, Y) {
    const m = X.length;
    const n = Y.length;
 
    // Initialize 2D memoization table with -1
    const memo = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(-1));
 
    function helper(i, j) {
        if (i === 0 || j === 0) return 0;
 
        if (memo[i][j] !== -1) return memo[i][j];
 
        if (X[i - 1] === Y[j - 1]) {
            memo[i][j] = 1 + helper(i - 1, j - 1);
        } else {
            memo[i][j] = Math.max(helper(i - 1, j), helper(i, j - 1));
        }
 
        return memo[i][j];
    }
 
    return helper(m, n);
}

3. Tabulation Implementation (Bottom-Up DP)

In the bottom-up approach, we fill a 2D table dp of size (m+1) x (n+1).

Tabulation Matrix for X = "AGGTAB", Y = "GXTXAYB"

ØGXTXAYB
Ø00000000
A00000111
G01111111
G01111111
T01122222
A01122333
B01122334
function lcsTabulation(X, Y) {
    const m = X.length;
    const n = Y.length;
 
    // Create a 2D table
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
 
    // Fill the table in bottom-up manner
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (X[i - 1] === Y[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
 
    return dp[m][n];
}
 
// Driver code
const X = "AGGTAB";
const Y = "GXTXAYB";
console.log("Length of LCS is:", lcsTabulation(X, Y));
// Output: Length of LCS is: 4

Complexity Analysis

  • Time Complexity: O(M * N)
    • Both top-down memoization and bottom-up tabulation solve each of the M * N subproblems exactly once in O(1) time.
  • Space Complexity: O(M * N)
    • Storing the 2D array table of size (M + 1) * (N + 1).
Introduction to DPCoin Change Problem