DSA AnimatorDSA animations
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.

How to solve Longest Common Subsequence

LeetCode 1143 · Medium · Dynamic Programming · Pattern: 2D String DP

Why the obvious approach is slow

Comparing every subsequence of one string with every subsequence of the other is exponential. Instead, compare prefixes.

The key idea

Let dp of i and j be the answer for the first i characters of the first string and the first j of the second. An empty prefix gives 0, so the first row and column are 0. If the two last characters match, take dp of i −1, j −1, plus 1. Otherwise, drop one character from either string, and take the larger of the two results. The bottom right cell is the answer.

Remember

Match means diagonal plus 1, mismatch means the larger of up and left. Prefix tables solve most two string problems.

Run the animation above on your own input, or watch the 1:52 video explanation of Longest Common Subsequence with a dry run and Java code.

More Dynamic Programming problems