1. 2D table row
Extra row and column represent empty prefixes.
Array(text2.length + 1).fill(0)Typorithm · medium
Longest Common Subsequence
▷ Interactive algorithm lablongest-common-subsequence-dpdynamic-programmingtwo-stringssubsequence2d-dp
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Longest Common Subsequence
Dynamic Programming
LCS uses a 2D table where each cell answers the best subsequence length for two prefixes.
Matching characters extend the diagonal result.
Different characters choose the better prefix after skipping one side.
The empty-prefix row and column make boundaries simple.
Preparing algorithm lab…
01
State: LCS length of prefixes i and j.
02
Match: diagonal + 1.
03
Mismatch: max(top, left).
04
Time O(m*n).
function longestCommonSubsequence(text1, text2) {
const dp = Array.from({ length: text1.length + 1 }, () =>
Array(text2.length + 1).fill(0),
);
for (let i = 1; i <= text1.length; i++) {
for (let j = 1; j <= text2.length; 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[text1.length][text2.length];
}Read the implementation
Connect each part of the code to the concept before you type.
2. Prefix loop
Each cell compares two prefixes.
for (let i = 1; i <= text1.length; i++)3. Matching chars
A match extends the diagonal subproblem.
dp[i][j] = dp[i - 1][j - 1] + 14. Skip one side
When chars differ, skip one char from either string.
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.