Quick Overview
LCS compares two strings as a grid: matching characters add 1 to the diagonal, mismatches inherit the better neighbour. The answer ends up in `dp[m][n]`, filled in `O(m * n)`.
"bcd" in "abcdef")."ace" is a subsequence of "abcde").Let dp[i][j] be the LCS length of text1[0...i-1] and text2[0...j-1]:
text1[i - 1] === text2[j - 1]):
dp[i][j] = 1 + dp[i - 1][j - 1]
- If characters differ:
```text
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
function longestCommonSubsequence(text1, text2) {
const m = text1.length;
const n = text2.length;
const dp = Array.from({ length: m + 1 }, () => new Array(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] = 1 + dp[i - 1][j - 1]; // Diagonal + 1
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // Max of top and left
}
}
}
return dp[m][n];
}
console.log(longestCommonSubsequence("abcde", "ace")); // Output: 3 ("ace")
console.log(longestCommonSubsequence("abc", "abc")); // Output: 3
console.log(longestCommonSubsequence("abc", "def")); // Output: 0
"" a c e
"" [ 0, 0, 0, 0 ]
a [ 0, 1, 1, 1 ]
b [ 0, 1, 1, 1 ]
c [ 0, 1, 2, 2 ]
d [ 0, 1, 2, 2 ]
e [ 0, 1, 2, 3 ] ◄── dp[5][3] = 3
dp[i][j] corresponds to 0-indexed string characters text1[i - 1] and text2[j - 1].Use 2D DP for string transformation and grid path problems. Next, let's explore the Intervals Pattern!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.