← Back to DSA Animator
Longest Common Subsequence LC #1143 Medium 2D DP
Problem

Given two strings text1 and text2, return the length of their longest common subsequence. Subsequence = delete some chars without changing order.

Example 1
Input: "abcde", "ace"
Output: 3
Match: dp[i][j]=dp[i-1][j-1]+1. No match: dp[i][j]=max(dp[i-1][j], dp[i][j-1]).
Try Examples
Custom:
Approach
2D DP — match → dp[i-1][j-1]+1, else max(up, left)
dp[i][j] = LCS of s[0..i-1] and t[0..j-1]. Match extends diagonal; mismatch takes best of skip s or skip t.
DP Table
Load an example to begin.
Variables
i, j
—
match?
—
up / left
—
dp[i][j]
—
Step Logic
Press ▶ Play or Next Step to begin.
🔗
Ready
0 / 0
Select an example and press Play.
Algorithm
1
dp[i][j] = LCS of s[0..i-1] and t[0..j-1]
2
Match: dp[i][j] = dp[i-1][j-1] + 1
3
No match: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
4
Answer = dp[m][n]
Time
O(m×n)
Space
O(m×n)
Why This Works

If chars match, extend LCS of shorter prefixes by 1. If not, take best of skipping one char from either string. Table fills bottom-up.