Course contentsShow
← Computer Science
Lesson 925 of 2,87222. Dynamic ProgrammingFree lesson

Longest Common Subsequence (LCS)

Find the longest subsequence common to two sequences using 2D DP table and recurrence relation.

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 1

    • dp[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.