Overview
Longest Common Subsequence: find the longest sequence of characters that appears in both strings in order.
Analogy
Two DNA strands sharing a genetic signature: find the longest common thread.
Step-by-step
- dp[i][j] = LCS length of s1[:i] and s2[:j].
- 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]).
- Answer is dp[m][n].
Visual
s1='ABCBD', s2='ACBD': dp table → LCS=3 ('ABD')
Common mistakes
- Confusing LCS (subsequence, non-contiguous) with Longest Common Substring (contiguous).
- Allocating (m+1)×(n+1) table but indexing from 0 incorrectly.
Practice questions
- Reconstruct the actual LCS string by backtracking.
- Compute edit distance (LCS-based relationship: ED = m+n-2*LCS).
Space
O(m×n), O(min(m,n)) with rolling rows
AI Wisdom