Longest Common Subsequence (LCS)
You'll learn how to find the longest sequence of characters that appears in the same order (but not necessarily consecutively) in two different strings using dynamic programming.
What Is a Subsequence?
A subsequence is a sequence derived from another by deleting some (or zero) characters without changing the order of remaining elements. For example, "ace" is a subsequence of "abcde" (we deleted 'b' and 'd').
The LCS problem asks: given two sequences, what's the longest subsequence they both share?
The Core Idea
Think of comparing two family trees to find common ancestors—you're looking for matches that appear in the same relative order in both lineages.
For strings X and Y, we build a 2D table where dp[i][j] represents the length of the LCS between the first i characters of X and the first j characters of Y.
The Recurrence Relation
The magic happens with this logic:
-
If characters match (
X[i-1] == Y[j-1]): the LCS grows by 1dp[i][j] = dp[i-1][j-1] + 1
-
If they don't match: take the best result from either ignoring one character from X or one from Y
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Base Cases
When either string is empty (i == 0 or j == 0), the LCS length is 0: dp[0][j] = dp[i][0] = 0
Example
For X = "ABCD" and Y = "ACBD", the table builds up to show that the LCS has length 3 ("ABD" or "ACD").
Key Takeaway: LCS uses a 2D DP table where each cell combines results from adjacent cells based on whether characters match, building up the optimal solution from overlapping subproblems.