Longest Common Subsequence
Problem
Return the length of the longest sequence of characters that appears, in order but not necessarily contiguously, in both strings.
Example 1
Input: a = "abcde", b = "ace" Output: 3
"ace".
Example 2
Input: a = "abc", b = "def" Output: 0
Also asked as: Find the longest common subsequence between two strings
Test cases
Case 1
Input: "abcde", "ace" Expected: 3
Case 2
Input: "abc", "def" Expected: 0
Case 3
Input: "abc", "abc" Expected: 3
View solutionHide solution1 approach
1. 2-D table
Time O(n · m)Space O(n · m)
If the last chars match, +1 on the diagonal; else take the best of dropping one char from either string.
function lcs(a, b) { const n = a.length, m = b.length; const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0)); for (let i = 1; i <= n; i++) for (let j = 1; j <= m; j++) dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]); return dp[n][m];}