Longest Common Subsequence (LCS)

Two-parameter DP on prefixes of X and Y: when last characters match, extend by 1; otherwise drop one character from one side and take the better.

Problem

You are given two sequences (think of them as strings) X = x₁x₂ … xₘ of length m and Y = y₁y₂ … yₙ of length n.

A subsequence of a sequence is what you get by deleting zero or more elements while keeping the order of the rest. A common subsequence of X and Y is a sequence that is a subsequence of both.

Your task: find the length of the longest common subsequence (LCS).

Example. X = "ABCBDAB", Y = "BDCABA". One LCS is "BCBA" (length 4). Another LCS of the same length is "BDAB". The LCS is not always unique, but its length is.

DP recurrence relation

Meaning of the state. Let lcs(i, j) = length of the LCS of the prefixes X[0 … i − 1] (the first i characters of X) and Y[0 … j − 1] (the first j characters of Y). Here 0 ≤ i ≤ m and 0 ≤ j ≤ n.

Idea in words. Compare the last characters of the two prefixes: X[i − 1] and Y[j − 1].

Case 1 — they match (X[i − 1] = Y[j − 1]). Then this character can be the last element of an LCS of the two prefixes. After taking it, you still have to find the best matching of X[0 … i − 2] and Y[0 … j − 2] — that is lcs(i − 1, j − 1). So one good option has length lcs(i − 1, j − 1) + 1.

Could the LCS instead not end with X[i − 1] = Y[j − 1]? You can show that whenever the last characters match, you never lose by including them, so we just take this case.
Case 2 — they differ (X[i − 1] ≠ Y[j − 1]). Then at least one of these two characters is not in the LCS. So either we shorten X's prefix by one — giving lcs(i − 1, j) — or we shorten Y's prefix by one — giving lcs(i, j − 1). We do not know which side to drop from, so try both and keep the best:

Putting it together:

Example

lcs(i, j) = lcs(i − 1, j − 1) + 1 if X[i − 1] = Y[j − 1]

lcs(i, j) = max( lcs(i − 1, j), lcs(i, j − 1) ) otherwise

Why this is correct. Every common subsequence of the two prefixes either (a) uses the last characters of both — only possible when they match, and then dropping them leaves a common subsequence of the smaller prefixes — or (b) does not use X[i − 1], so it is a subsequence of X[0 … i − 2] vs Y[0 … j − 1], or (c) does not use Y[j − 1], so it is a subsequence of X[0 … i − 1] vs Y[0 … j − 2]. Cases (b) and (c) are exactly the two max options.

DP memoization

Use a 2D table memo[0 … m][0 … n] with −1 for “not computed yet.”

If memo[i][j] is set, return it.
Otherwise compute lcs(i, j) with the recurrence (it calls (i − 1, j − 1) in the match case, or (i − 1, j) and (i, j − 1) in the mismatch case), store the answer in memo[i][j], and return.

There are (m + 1)(n + 1) states, each with O(1) extra work, giving O(m · n) time and O(m · n) space. Recursion depth is at most m + n.

(To reconstruct the LCS string itself, walk the filled table backwards from (m, n): take the matching character whenever X[i − 1] = Y[j − 1]; otherwise step into whichever neighbour gave the max.)

DP base case

If either prefix is empty, the LCS is empty:

Example

lcs(0, j) = 0 for every j = 0 … n

lcs(i, 0) = 0 for every i = 0 … m

Explanation. With nothing on one side there are no characters to match. Every recursion eventually reaches one of these base cases because each step decreases i + j by at least one.

Worked example

Take X = "AGCAT" (m = 5) and Y = "GAC" (n = 3). Build the 6 × 4 table lcs(i, j) by rows.

We label rows by characters of X (row 0 is empty prefix) and columns by characters of Y (column 0 is empty prefix):

Example

ε G A C

ε | 0 0 0 0

A | 0 0 1 1

G | 0 1 1 1

C | 0 1 1 2

A | 0 1 2 2

T | 0 1 2 2

A few entries explained:

lcs(1, 2) compares X[0] = 'A' and Y[1] = 'A' — match. = lcs(0, 1) + 1 = 0 + 1 = 1.
lcs(2, 1) compares X[1] = 'G' and Y[0] = 'G' — match. = lcs(1, 0) + 1 = 0 + 1 = 1.
lcs(3, 3) compares X[2] = 'C' and Y[2] = 'C' — match. = lcs(2, 2) + 1 = 1 + 1 = 2.
lcs(4, 2) compares X[3] = 'A' and Y[1] = 'A' — match. = lcs(3, 1) + 1 = 1 + 1 = 2.
lcs(5, 3) compares X[4] = 'T' and Y[2] = 'C' — mismatch. = max(lcs(4, 3), lcs(5, 2)) = max(2, 2) = 2.

The answer is lcs(5, 3) = 2, matching common subsequences such as "AC" or "GC" or "GA".

Pseudocode

Read LCS(i, j) as “the LCS length of the first i characters of X and the first j characters of Y.” One comparison decides everything: if the last characters of the two prefixes match, take that character and shrink both prefixes; if they differ, drop the last character from one side or the other and keep the better result.

1LCS(i, j, X, Y, memo)             // LCS of first i chars of X, first j of Y
2  if i == 0 or j == 0             // an empty prefix matches nothing
3    return 0
4  if memo[i][j] != UNKNOWN        // already solved? reuse the answer
5    return memo[i][j]
6  if X[i - 1] == Y[j - 1]         // last characters match → take them
7    memo[i][j] = LCS(i - 1, j - 1, X, Y, memo) + 1
8  else                            // mismatch → drop a char from one side
9    a = LCS(i - 1, j,     X, Y, memo)   // option 1: drop last char of X
10    b = LCS(i,     j - 1, X, Y, memo)   // option 2: drop last char of Y
11    memo[i][j] = max(a, b)              // keep the better option
12  return memo[i][j]

Complexity

Time: O(m · n) — each of the (m + 1)(n + 1) states does constant extra work. Space: O(m · n) for the memo. Recursion depth is at most m + n.

Complexity Analysis

Time Complexity

O(m · n)

Space Complexity

O(m · n) for memo

Reconstruction of the LCS string itself is O(m + n) extra work

Growth Rate Comparison

Problem

You are given two sequences (think of them as strings) X = x₁x₂ … xₘ of length m and Y = y₁y₂ … yₙ of length n.

Your task: find the length of the longest common subsequence (LCS).

Example. X = "ABCBDAB", Y = "BDCABA". One LCS is "BCBA" (length 4). Another LCS of the same length is "BDAB". The LCS is not always unique, but its length is.

DP recurrence relation

Idea in words. Compare the last characters of the two prefixes: X[i − 1] and Y[j − 1].

Case 1 — they match (X[i − 1] = Y[j − 1]). Then this character can be the last element of an LCS of the two prefixes. After taking it, you still have to find the best matching of X[0 … i − 2] and Y[0 … j − 2] — that is lcs(i − 1, j − 1). So one good option has length lcs(i − 1, j − 1) + 1.

Could the LCS instead not end with X[i − 1] = Y[j − 1]? You can show that whenever the last characters match, you never lose by including them, so we just take this case.
Case 2 — they differ (X[i − 1] ≠ Y[j − 1]). Then at least one of these two characters is not in the LCS. So either we shorten X's prefix by one — giving lcs(i − 1, j) — or we shorten Y's prefix by one — giving lcs(i, j − 1). We do not know which side to drop from, so try both and keep the best:

Putting it together:

Example

lcs(i, j) = lcs(i − 1, j − 1) + 1 if X[i − 1] = Y[j − 1]

lcs(i, j) = max( lcs(i − 1, j), lcs(i, j − 1) ) otherwise

DP memoization

Use a 2D table memo[0 … m][0 … n] with −1 for “not computed yet.”

If memo[i][j] is set, return it.
Otherwise compute lcs(i, j) with the recurrence (it calls (i − 1, j − 1) in the match case, or (i − 1, j) and (i, j − 1) in the mismatch case), store the answer in memo[i][j], and return.

There are (m + 1)(n + 1) states, each with O(1) extra work, giving O(m · n) time and O(m · n) space. Recursion depth is at most m + n.

DP base case

If either prefix is empty, the LCS is empty:

Example

lcs(0, j) = 0 for every j = 0 … n

lcs(i, 0) = 0 for every i = 0 … m

Explanation. With nothing on one side there are no characters to match. Every recursion eventually reaches one of these base cases because each step decreases i + j by at least one.

Worked example

Take X = "AGCAT" (m = 5) and Y = "GAC" (n = 3). Build the 6 × 4 table lcs(i, j) by rows.

We label rows by characters of X (row 0 is empty prefix) and columns by characters of Y (column 0 is empty prefix):

Example

ε G A C

ε | 0 0 0 0

A | 0 0 1 1

G | 0 1 1 1

C | 0 1 1 2

A | 0 1 2 2

T | 0 1 2 2

A few entries explained:

lcs(1, 2) compares X[0] = 'A' and Y[1] = 'A' — match. = lcs(0, 1) + 1 = 0 + 1 = 1.
lcs(2, 1) compares X[1] = 'G' and Y[0] = 'G' — match. = lcs(1, 0) + 1 = 0 + 1 = 1.
lcs(3, 3) compares X[2] = 'C' and Y[2] = 'C' — match. = lcs(2, 2) + 1 = 1 + 1 = 2.
lcs(4, 2) compares X[3] = 'A' and Y[1] = 'A' — match. = lcs(3, 1) + 1 = 1 + 1 = 2.
lcs(5, 3) compares X[4] = 'T' and Y[2] = 'C' — mismatch. = max(lcs(4, 3), lcs(5, 2)) = max(2, 2) = 2.

The answer is lcs(5, 3) = 2, matching common subsequences such as "AC" or "GC" or "GA".

Pseudocode

1LCS(i, j, X, Y, memo)             // LCS of first i chars of X, first j of Y
2  if i == 0 or j == 0             // an empty prefix matches nothing
3    return 0
4  if memo[i][j] != UNKNOWN        // already solved? reuse the answer
5    return memo[i][j]
6  if X[i - 1] == Y[j - 1]         // last characters match → take them
7    memo[i][j] = LCS(i - 1, j - 1, X, Y, memo) + 1
8  else                            // mismatch → drop a char from one side
9    a = LCS(i - 1, j,     X, Y, memo)   // option 1: drop last char of X
10    b = LCS(i,     j - 1, X, Y, memo)   // option 2: drop last char of Y
11    memo[i][j] = max(a, b)              // keep the better option
12  return memo[i][j]

Complexity

Time: O(m · n) — each of the (m + 1)(n + 1) states does constant extra work. Space: O(m · n) for the memo. Recursion depth is at most m + n.

Complexity Analysis

Time Complexity

O(m · n)

Space Complexity

O(m · n) for memo

Reconstruction of the LCS string itself is O(m + n) extra work