Find the longest sequence of characters that appears in both strings in the same relative order (not necessarily contiguous). A classic 2D dynamic-programmingtable lets you build the answer in O(m × n) with a single elegant recurrence: match → diagonal + 1, no-match → max of up or left.
Given two strings, return the length of their longest common subsequence (LCS) — a subsequence that appears in both strings in the same relative order, but not necessarily contiguously. text1="abcde", text2="ace" → 3 (the subsequence "ace"appears in both). text1="abc", text2="abc" → 3. text1="abc", text2="def" → 0.
dp[i][j] as the LCS length of text1[0..i-1] and text2[0..j-1]. The recurrence has only two cases:dp[i][j] = dp[i-1][j-1] + 1 — the LCS extends diagonally.dp[i][j] = max(dp[i-1][j], dp[i][j-1]) — skip one character from either string, take the better result.(m+1)×(n+1) table, all zeros. The extra row and column represent the empty-string base cases: LCS with an empty string is 0.text1[i-1] and text2[j-1].dp[i][j] = dp[i-1][j-1] + 1. The diagonal inherits the best LCS of both shorter prefixes, plus this shared character.dp[i][j] = max(dp[i-1][j], dp[i][j-1]). We can only skip one character; take the skip that left the longer LCS.dp[m][n] is the final result. Backtrace diagonally whenever a match drove the value to recover the actual subsequence.dp[i][j] = 0 instead of max(up,left)); the answer is the table maximum, not the corner cell.Because each row only looks at the row above, you can keep two 1-D arrays — prev and curr— cutting space from O(m × n) to O(n). A single-array version is also possible with a diagonal save variable. Note: you lose backtrace ability with rolling rows.
dp[i][j] = length of the LCS of the first i chars of “abcde” and the first jchars of “ace”. Base cases (row 0 and col 0) are already 0.function longestCommonSubsequence(text1: string, text2: string): number {
const m = text1.length;
const n = text2.length;
// dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]
const dp: number[][] = Array.from({ length: m + 1 }, () => new Array<number>(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1; // match: extend diagonal
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // no match: best of up/left
}
}
}
return dp[m][n];
}(m+1)×(n+1) table filled with zeros. Row 0 and column 0 model the empty-prefix base cases: LCS of any string with the empty string is 0.dp[i][j]only reads cells above and to the left, they're already filled when we need them.text1[i-1] === text2[j-1] the two characters can extend the LCS of the two shorter prefixes. We inherit the diagonal value and add 1.max(dp[i-1][j], dp[i][j-1]) picks the skip that preserves the longest LCS found so far.dp[m][n]is the LCS length of the full strings. To recover the actual subsequence, backtrace: whenever the match branch drove a cell's value, step diagonally and record that character.dp[m][n]: whenever text1[i-1] === text2[j-1] drove the value, prepend that char and step diagonally; otherwise move toward the larger neighbour.prev and curr — swapping each iteration. A single-array solution uses a diag temp variable.text1 with its reverse — same code, different inputs.| "longest common subsequence / LCS" | 2D DP table, m×n |
| two strings, order matters, gaps allowed | dp[i][j] = diagonal or max(up,left) |
| backtrace for actual subsequence | follow diagonal on matches from dp[m][n] |
| palindromic subsequence / supersequence | LCS of string with reverse / derived from LCS |
function longestCommonSubsequence(text1: string, text2: string): number {
const m = text1.length, n = text2.length;
const dp = Array.from({ length: m + 1 }, () => new Array<number>(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[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]);
}
}
}
return dp[m][n];
}dp[i][j] when text1[i-1] === text2[j-1]?dp[i][j] depend on when there is no match?