Longest Common Subsequence
Watch how 2D dynamic programming finds the longest common subsequence between two strings by building a table step by step.
Time: O(m × n)
Space: O(m × n)
2D DP Table
Backtracking
Fast (300ms)Slow (2000ms)
Progress: Step 1 of 0Phase: start
Strings Being Compared
String 1:
A
B
C
D
G
H
String 2:
A
E
D
F
H
R
DP Table
Current Step:
Click Start to begin the LCS visualization
Algorithm Details
Time Complexity:
O(m × n)Space Complexity:
O(m × n)Type:2D DP
Space Optimized:O(min(m,n))
Real-world Applications
- •DNA sequence alignment in bioinformatics
- •File difference detection (diff tools)
- •Version control systems (Git)
- •Text similarity and plagiarism detection
- •Data compression algorithms
- •Spell checkers and autocorrect
Key DP Concepts
- ✓2D Table: dp[i][j] = LCS length of first i and j characters
- ✓Match: If chars match, dp[i][j] = dp[i-1][j-1] + 1
- ℹNo Match: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- ℹBase Case: Empty string has LCS length 0
Related DP Problems
- •Longest Common Substring
- •Edit Distance (Levenshtein)
- •Longest Increasing Subsequence
- •Sequence Alignment
- •Maximum Palindromic Subsequence