Question

How to find the length of the longest common subsequence (LCS) in two strings with JavaScript

Answer 1

function mymax(a, b) {
    return (a > b) ? a : b;
}
  
function lcs(s1, s2, s1_len, s2_len) {
    if (s1_len == 0 || s2_len == 0) {
        return 0;
    }
    if (s1[s1_len - 1] == s2[s2_len - 1]) {
        return 1 + lcs(s1, s2, s1_len - 1, s2_len - 1);
    }
    else {
        return mymax(lcs(s1, s2, s1_len, s2_len - 1), lcs(s1, s2, s1_len - 1, s2_len));
    }
}
   
   
var s1 = "accyrb";
var s2 = "cyxyazb";
 
document.write("The length of LCS is: " + lcs(s1, s2, s1.length, s2.length));


/*
run:
    
The length of LCS is: 3 
    
*/

 

70+ SQL courses for beginners and professionals

Answer 2

/*
    This program computes BOTH:
      1. The length of the Longest Common Subsequence (LCS)
      2. The actual LCS subsequence

    It uses an efficient dynamic‑programming algorithm:
        Time:  O(n * m)
        Space: O(n * m)

    dp[i][j] stores the LCS length between:
        s1[0..i-1] and s2[0..j-1]

    Recurrence:
        If characters match:
            dp[i][j] = dp[i-1][j-1] + 1
        Else:
            dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])

    After filling the DP table, we reconstruct the LCS by
    walking backwards from dp[n][m].
*/

function lcs(s1, s2) {
    const n = s1.length;
    const m = s2.length;

    // Create DP table initialized with zeros
    const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));

    // Fill DP table
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (s1[i - 1] === s2[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 LCS sequence
    let length = dp[n][m];
    let lcsChars = new Array(length);

    let i = n, j = m, index = length - 1;

    while (i > 0 && j > 0) {
        if (s1[i - 1] === s2[j - 1]) {
            // Character is part of LCS
            lcsChars[index] = s1[i - 1];
            index--;
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--; // Move up
        } else {
            j--; // Move left
        }
    }

    return { length, sequence: lcsChars.join("") };
}

// Usage
const s1 = "AGGTAB";
const s2 = "GXTXAYB";

const result = lcs(s1, s2);

console.log("String 1:", s1);
console.log("String 2:", s2);
console.log("Length of LCS:", result.length);
console.log("LCS sequence:", result.sequence);


/*
run:

String 1: AGGTAB
String 2: GXTXAYB
Length of LCS: 4
LCS sequence: GTAB

*/

 

70+ SQL courses for beginners and professionals