Longest Common Subsequence (LCS)

Question 1

If characters match at dp[i][j], where does the value come from?

Accepted Answer

Diagonal cell — When characters match, we extend the LCS found so far in the prefixes excluding these characters (diagonal).

Question 2

The Longest Common Subsequence (LCS) of two strings is…

Accepted Answer

The longest shared sequence preserving relative order — A subsequence keeps relative order but allows gaps; LCS finds the longest such shared sequence — unlike the longest common SUBSTRING, which must be contiguous.

Question 3

The LCS DP recurrence, when characters match (A[i]==B[j]), sets dp[i][j] =

Accepted Answer

dp[i-1][j-1] + 1 — On a match, extend the LCS of the prefixes by one: dp[i][j] = dp[i-1][j-1] + 1.

Question 4

When characters DON'T match, dp[i][j] =

Accepted Answer

The larger of the two neighbors — Without a match, the LCS is the better of dropping a character from either string: max(dp[i-1][j], dp[i][j-1]).

Question 5

What is the time and space complexity of the standard LCS DP for strings of length m and n?

Accepted Answer

O(m·n) time and O(m·n) space — The DP fills an (m+1)×(n+1) table, each cell in O(1): O(mn) time and space (space reducible to O(min(m,n))).

Question 6

LCS can be space-optimized to…

Accepted Answer

O(min(m,n)) using two rolling rows — Only the previous row is needed to compute the current one, so two rows of length min(m,n)+1 suffice — O(min(m,n)) space (Hirschberg's gives O(min) even for reconstruction).

Question 7

LCS is closely related to which other string DP?

Accepted Answer

Edit distance — Edit distance uses a nearly identical DP table; LCS length even bounds certain edit operations (insertions/deletions to transform one string into another).

Question 8

The 'diff' utility and version-control change detection are based on…

Accepted Answer

Longest common subsequence of both file versions — Treating lines as tokens, the LCS marks unchanged lines; the rest are insertions/deletions — the core of diff and merge tools.

Question 9

To RECONSTRUCT the actual LCS (not just its length), you…

Accepted Answer

Backtrack from dp[m][n], diagonal on matches — Starting at the bottom-right, diagonal moves (matches) emit characters; non-matches follow the direction of the larger value, tracing the LCS in reverse.

Question 10

What are the base cases of the LCS table?

Accepted Answer

First row and column entries are all zero — An empty prefix has no common subsequence with anything, so the first row and column are zero — anchoring the recurrence.

The LCS recurrence

Test your knowledge

If characters match at dp[i][j], where does the value come from?

The short version

In more depth

String Alignment

When to reach for this

Interview Questions

References & Further Reading

Related topics

Love this visualization?