1function longestCommonSubsequence(str1, str2) {
2 const m = str1.length, n = str2.length;
3 const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
4
5 for (let i = 1; i <= m; i++) {
6 for (let j = 1; j <= n; j++) {
7 if (str1[i - 1] === str2[j - 1]) {
8 dp[i][j] = 1 + dp[i - 1][j - 1]; // Match!
9 } else {
10 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // Mismatch
11 }
12 }
13 }
14
15 // Traceback to construct LCS
16 let i = m, j = n, lcs = [];
17 while (i > 0 && j > 0) {
18 if (str1[i - 1] === str2[j - 1]) {
19 lcs.unshift(str1[i - 1]);
20 i--; j--; // Move diagonal
21 } else if (dp[i - 1][j] >= dp[i][j - 1]) {
22 i--; // Move up
23 } else {
24 j--; // Move left
25 }
26 }
27 return { length: dp[m][n], lcs: lcs.join('') };
28}