3.7.10 · D5Algorithm Paradigms
Question bank — DP problems — Longest Common Subsequence (LCS)
First: the notation this page uses
Before any question, let us build every symbol from zero so nothing on this page is a mystery.
Now every symbol below — , , , , , — and every direction word points at something you have already seen drawn.
True or false — justify
The LCS of two strings is always contiguous in at least one of them.
False. LCS characters may be scattered with gaps in both strings — e.g.
AC is the LCS of ABC and AXC, and it is contiguous in neither. Contiguity is the Longest Common Substring condition, not this one.If two strings share no characters at all, their LCS length is 0.
True. With no common character there is nothing to keep in order; every cell filled by mismatch inherits neighbours that all trace back to the zero base row/column, so .
The LCS is unique for any pair of strings.
False. Ties happen:
ABC and ACB have LCS length 2 with two valid answers AB and AC. Only the length is unique; the string is not.Reversing both strings changes the LCS length.
False. LCS length is symmetric under reversing both inputs, because a common subsequence read backwards is still a common subsequence of the reversed strings — same length.
Swapping the two input strings () can change the LCS length.
False. ; the recurrence is symmetric in its two arguments (the grid just transposes), so the corner value is identical.
The LCS length can exceed the length of the shorter string.
False. A common subsequence is a subsequence of both, so it cannot be longer than either input: (recall , ).
If is a subsequence of , then .
True. itself is common to both (it lies inside in order), and nothing can beat by the bound above, so the LCS is exactly .
Every diagonal step in the traceback adds a character to the answer.
True — but only diagonal steps taken on a match. A diagonal move only occurs when , which is precisely when a shared character is recorded, so match-diagonals and answer-characters are in one-to-one correspondence.
The final answer is the maximum value anywhere in the DP table.
False for LCS — the answer is always the corner . Taking the table-wide max is the rule for Longest Common Substring, which resets to 0 on mismatch.
Two strings of equal length always have LCS equal to that length only if the strings are identical.
True. forces the whole of to be a common subsequence of an equally long , which is only possible if character for character.
Spot the error
"On a mismatch, ."
The stray is wrong. Mismatches add no character; the correct rule is (the up/left arrows in figure s03). You only earn on a diagonal match.
"On a match, ."
Wrong neighbour. A match extends the diagonal prefix that excludes both matched characters: . Using up/left double-counts a character.
"I dropped the extra zero row and column and indexed off and ."
Off-by-one bug. With code's 0-indexed strings, cell must compare and , and the padding zero row/column implements the empty-prefix base case .
"Since ABAB and BABA are anagrams, their LCS is length 4."
Anagrams share letters but not necessarily order. Their LCS is
BAB (length 3): you cannot keep all four while preserving relative order in both."I filled the table but forgot the base row, initializing to 1."
An empty prefix has no common subsequence, so . Seeding 1 leaks a phantom character into every downstream cell.
"On a mismatch tie (), I must pick 'up' or the answer is wrong."
False constraint. Either direction gives an equally long valid LCS; the tie only affects which string you recover during traceback, never the length.
"Longest Increasing Subsequence is unrelated to LCS."
Longest Increasing Subsequence reduces to LCS of the array and its sorted-unique copy, so they are directly linked, not unrelated.
Why questions
Why does a match let us safely add the pair without risking a shorter answer?
Because any optimal LCS of the prefixes can be rewritten to end with this matching pair without losing length (an exchange argument): if the optimum did not use the pair, swap its last kept letter for this pair — same length, still valid. So pairing is never worse, and it shrinks both prefixes by one.
Why do we look up-left (diagonal) specifically on a match?
A match consumes one character from each string, so we must recurse on both prefixes shortened by one — that cell sits diagonally at , exactly the diagonal arrow in figure s03.
Why is it safe to discard one endpoint on a mismatch?
Since , an LCS cannot end in both, so at least one is useless as a final character; dropping the less-useful one loses nothing, and picks the better branch (the up vs left arrows).
Why is LCS an algorithm and not exponential like brute force?
There are only distinct prefix subproblems — one per grid cell; DP computes each once and reuses it, collapsing the exponential tree of choices into a filled grid.
Why can space be reduced to ?
Each cell needs only the current and previous row (up, left, diagonal all live within two rows), so we roll two rows and keep the shorter dimension as the row length.
Why does Edit Distance use the same grid but a different recurrence?
Both walk an prefix grid, but Edit Distance also allows substitute/insert/delete moves with costs, so its cell combines three neighbours with penalties rather than LCS's match-reward.
Edge cases
What is the LCS when both strings are empty?
Length 0. With the only cell is by the base case — there are no letters, so nothing common; this is the corner-stone every other cell traces back to.
What is the LCS when exactly one string is empty?
Length 0. The empty-prefix base case handles it directly — one side supplies no characters, so nothing can be common.
What is the LCS of a string with itself?
The whole string, length . Every character matches on the diagonal, so the traceback walks the main diagonal and recovers in full.
What is the LCS when the strings are reverses of each other, like ABC and CBA?
Length 1 here (any single shared letter), because keeping any two letters in order in one forces the opposite order in the other. In general it is the longest palindromic-style common ordering, often just 1.
What happens with repeated characters, e.g. AAAA and AA?
LCS length 2. Repeats are fine; you match as many
As in order as the shorter string can supply, bounded by .What if both strings are identical single characters, A and A?
Length 1. One match on the only diagonal cell gives .
What if the strings share characters but in fully reversed order and length grows — does the table still terminate correctly?
Yes. Regardless of content, the table is finite and every cell depends only on already-filled up/left/diagonal neighbours, so filling always terminates with the answer at the corner.
Recall One-line survival kit
Match → diagonal ; miss → ; base (including both-empty); answer at corner ; length unique, string not; bounded by .
Connections
- Parent topic — the full LCS derivation these traps attack.
- Dynamic Programming — the grid-filling mindset assumed throughout.
- Longest Common Substring — the contiguous cousin that resets on mismatch (source of the biggest trap).
- Edit Distance — same grid, richer moves.
- Longest Increasing Subsequence — reduces to LCS.