Skip to content
← All Patterns
← Unbounded KnapsackDP on Trees →
Dynamic ProgrammingIntermediate

Longest Common Subsequence

Compare two sequences and build a 2D DP table where each cell represents the optimal answer for prefixes of both sequences.

Problem: Longest Common Subsequence

Find the length of the LCS between "ABCDE" and "ACE" using a 2D DP table.

∅ACE
∅
0
0
0
0
A
0
0
0
0
B
0
0
0
0
C
0
0
0
0
D
0
0
0
0
E
0
0
0
0
DefaultComputedActiveResult

Initialize: DP table with base case

Create (m+1)×(n+1) table. Row 0 and col 0 = 0 (empty string has LCS 0).

Step 1/17
Speed:

When to Use

  • Compare two strings/sequences
  • Edit distance
  • Longest common substring
  • Interleaving strings

Key Indicators

  • Two strings/sequences
  • Match/skip decisions
  • 2D DP table
  • Edit distance

Complexity

Time

O(m × n)

Space

O(m × n) or O(min(m,n))

Common Problems

Longest Common SubsequenceEdit DistanceMinimum ASCII Delete SumLongest Palindromic Subsequence

Code

dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
    for j in range(1, n+1):
        if s1[i-1] == s2[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Want all 29 patterns with detailed visual walkthroughs?

The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.

Book Coming Soon ($4.99)