Longest Common Subsequence Algorithm

The Longest Common Subsequence (LCS) problem involves finding the longest subsequence that appears in both given strings. Unlike substrings, subsequences are not required to occupy consecutive positions within the original strings.

Given two strings, the LCS problem requires finding the longest sequence of characters that are present in both strings in the same relative order but not necessarily contiguous. Solving this problem efficiently is essential for various applications, including plagiarism detection, DNA sequence alignment, and revision control systems.

function longestCommonSubsequence(str1, str2) {
    const m = str1.length;
    const n = str2.length;
    const dp = Array.from({ length: m + 1 }, () => 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]);
            }
        }
    }
    let i = m, j = n;
    const result = [];
    while (i > 0 && j > 0) {
        if (str1[i - 1] === str2[j - 1]) {
            result.unshift(str1[i - 1]);
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    return result.join('');
}

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

The time complexity of the LCS algorithm is O(m * n), where m and n are the lengths of the input strings.

By understanding its principles and implementing efficient algorithms like dynamic programming, developers can effectively solve the LCS problem and tackle related challenges in diverse fields.