/*
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: string, s2: string): { length: number; sequence: string } {
const n: number = s1.length;
const m: number = s2.length;
// Create DP table initialized with zeros
const dp: number[][] = Array.from({ length: n + 1 }, () =>
Array(m + 1).fill(0)
);
// Fill DP table
for (let i: number = 1; i <= n; i++) {
for (let j: number = 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
const length: number = dp[n][m];
const lcsChars: string[] = new Array(length);
let i: number = n;
let j: number = m;
let index: number = 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: string = "AGGTAB";
const s2: string = "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
*/
