Longest Common Subsequence (LCS)

The Longest Common Subsequence (LCS) algorithm is a dynamic programming technique used to find the longest subsequence common to two sequences.

A subsequence is a sequence that appears in the same relative order but not necessarily contiguous.

pseudocode:

function LCS_length(X[1..m], Y[1..n]):
    // Initialize a 2D array to store lengths of LCSs
    let c[0..m, 0..n] be a new array

    // Initialize the first row and first column of the array to 0
    for i from 0 to m:
        c[i,0] = 0
    for j from 0 to n:
        c[0,j] = 0

    // Fill the array using dynamic programming
    for i from 1 to m:
        for j from 1 to n:
            if X[i] == Y[j]:
                c[i,j] = c[i-1,j-1] + 1
            else:
                c[i,j] = max(c[i-1,j], c[i,j-1])

    // Return the length of the LCS
    return c[m,n]

function print_LCS(c[0..m, 0..n], X[1..m], Y[1..n], i, j):
    if i == 0 or j == 0:
        return
    if X[i] == Y[j]:
        print_LCS(c, X, Y, i-1, j-1)
        print X[i]
    else if c[i-1,j] > c[i,j-1]:
        print_LCS(c, X, Y, i-1, j)
    else:
        print_LCS(c, X, Y, i, j-1)

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

    // Initialize a 2D array to store the lengths of LCS
    const lcsLengths = Array.from(Array(m + 1), () => Array(n + 1).fill(0));

    // Build the LCS length table using dynamic programming
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (str1[i - 1] === str2[j - 1]) {
                lcsLengths[i][j] = lcsLengths[i - 1][j - 1] + 1;
            } else {
                lcsLengths[i][j] = Math.max(lcsLengths[i - 1][j], lcsLengths[i][j - 1]);
            }
        }
    }

    // Trace back to construct the LCS string
    let i = m;
    let j = n;
    let lcs = '';
    while (i > 0 && j > 0) {
        if (str1[i - 1] === str2[j - 1]) {
            lcs = str1[i - 1] + lcs;
            i--;
            j--;
        } else if (lcsLengths[i - 1][j] > lcsLengths[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    return lcs;
}

// Example usage:
const str1 = "ABCBDAB";
const str2 = "BDCAB";
console.log("Longest Common Subsequence:", longestCommonSubsequence(str1, str2)); // Output: "BCAB"

In this example:

• We define a function longestCommonSubsequence that takes two strings, str1 and str2, as input.

• We initialize a 2D array lcsLengths to store the lengths of LCS of substrings of str1 and str2.

• We iterate through the strings using nested loops, comparing characters and updating the LCS lengths accordingly.

• After building the LCS length table, we trace back from the bottom-right corner to construct the LCS string.

• Finally, we return the LCS string.

In the example usage, str1 is "ABCBDAB" and str2 is "BDCAB", and the LCS is "BCAB".