DP problems — Longest Common Subsequence (LCS): Exercises

Two figures below show how a single cell is computed and how the diagonal "match" travels.

Figure — DP problems — Longest Common Subsequence (LCS)

Level 1 — Recognition

L1.1 Which of these is a subsequence of ABCDE (keeps order, gaps allowed)? For each, answer yes/no: ACE, AEC, BD, EDCBA, `` (empty).

Recall Solution L1.1

Read left-to-right; a subsequence must keep the relative order of ABCDE.

ACE → yes (A…C…E all in order).
AEC → no (E comes before C, order broken).
BD → yes (B…D).
EDCBA → no (reversed order).
`` empty → yes (delete everything; the empty string is a subsequence of every string).

Yes-count = 3.

L1.2 Without building a full table, state the LCS length of each pair by inspection: (a) ABC vs ABC (b) ABC vs XYZ (c) AAAA vs AA (d) `` vs HELLO.

Recall Solution L1.2

(a) identical strings → the whole string is common → length 3.
(b) no shared letter → length 0.
(c) AA fits inside AAAA in order → length 2 (you can never beat the shorter string's length).
(d) empty prefix → base case $L (0, j) = 0$ → length 0.

Level 2 — Application

L2.1 Fill the DP table for $X =$ AXY, $Y =$ AYZ and report $L (3, 3)$ .

Recall Solution L2.1

Rows = $X =$ AXY, cols = $Y =$ AYZ. Extra zero row/column for the empty prefix.

	A	Y	Z
""	0	0	0
A	1	1	1
X	1	1	1
Y	1	2	2

Cell (A,A): match → $1 + L (0, 0) = 1$ .
Cell (Y,Y): match → $1 + L ("AX", "A") = 1 + 1 = 2$ .
All mismatch cells inherit $max (up, left)$ .

Answer $L (3, 3) = 2$ , LCS = AY.

L2.2 For $X =$ AGGTAB, $Y =$ GXTXAYB (the parent's Worked Example 1), the corner is 4. Give the LCS string by traceback and list the indices used in each string.

Recall Solution L2.2

Walk from the bottom-right corner. Match → step diagonally and prepend the letter; mismatch → move toward the larger neighbour.

Following the built table, the matched pairs (1-indexed) are:

G : $x_{2} = y_{1}$
T : $x_{4} = y_{3}$
A : $x_{5} = y_{5}$
B : $x_{6} = y_{7}$

Prepending as we go bottom-up gives GTAB, length 4.

$X$ indices used: ${2, 4, 5, 6}$ . $Y$ indices used: ${1, 3, 5, 7}$ .

L3.1 True or false, with a one-line reason each: (a) LCS length is always $\leq min (m, n)$ . (b) If every letter of $X$ is distinct and $X$ is a permutation of $Y$ , then $L (m, n) = m$ . (c) Swapping the two input strings changes the LCS length.

Recall Solution L3.1

(a) True. The LCS is a subsequence of both, so it cannot be longer than the shorter string. If $X$ has $m$ letters you can't select more than $m$ of them.
(b) False. A permutation reorders letters; order can be broken. Example: $X =$ AB, $Y =$ BA are permutations but $L = 1$ , not $2$ .
(c) False. $L (i, j)$ is symmetric: the recurrence treats matches and the two neighbours identically after a swap, so $LCS (X, Y) = LCS (Y, X)$ . Swapping just transposes the table.

L3.2 Consider ABCBDAB vs BDCAB. The corner is 4 and there are multiple LCSs of length 4 (BCAB and BDAB). Explain where in the traceback the branching happens and why both are valid.

Recall Solution L3.2

During traceback, a tie occurs whenever the current mismatch cell had $L (up) = L (left)$ . At that fork you may go up or left, and each direction leads to an equally long LCS.

For ABCBDAB vs BDCAB, after committing the final B, you reach a cell where "keep the C-branch" and "keep the D-branch" both hold value 3. Choosing the C route builds BCAB; choosing the D route builds BDAB.

Both are valid because the recurrence only guarantees length optimality, not uniqueness — ties mean several optimal witnesses exist. The corner value $L (m, n) = 4$ is unique; the string is not.

Level 4 — Synthesis

L4.1 (LCS ↔ deletions) You may only delete characters. Given $X =$ AGGTAB ( $m = 6$ ) and $Y =$ GXTXAYB ( $n = 7$ ) with $L = 4$ , how many deletions are needed to turn both strings into their common subsequence? Give a formula and the number.

Recall Solution L4.1

Every character not part of the LCS must be deleted. From $X$ we keep $L$ letters and delete $m - L$ ; from $Y$ we delete $n - L$ . $deletions = (m - L) + (n - L) = m + n - 2 L .$ Here $= 6 + 7 - 2 (4) = 13 - 8 = 5$ .

This is exactly the deletion-only Edit Distance: $m + n - 2 L$ .

L4.2 (LIS via LCS) You are told LIS can be computed as an LCS. Given the array $A = [3, 1, 2, 1, 3]$ , construct the two strings whose LCS gives the LIS length, then compute it.

Recall Solution L4.2

Construction: let $B =$ sorted unique values of $A$ . Then $LIS (A) = LCS (A, B)$ , because a common subsequence of $A$ and the sorted-unique list is a subsequence of $A$ that is also strictly increasing.

$A = [3, 1, 2, 1, 3]$
$B = sorted unique = [1, 2, 3]$

Now compute $LCS ([3, 1, 2, 1, 3], [1, 2, 3])$ :

	1	2	3
""	0	0	0
3	0	0	1
1	1	1	1
2	1	2	2
1	1	2	2
3	1	2	3

LIS length = 3 (the increasing subsequence 1,2,3).

Level 5 — Mastery

L5.1 (Space optimization) The parent uses $O (mn)$ space. Explain why only two rows (or one rolling row) are ever needed to compute the length, and state the reduced space complexity. Which capability do you lose?

Recall Solution L5.1

Look at the recurrence: cell $L (i, j)$ depends only on row $i$ (its left neighbour $L (i, j - 1)$ ) and row $i - 1$ (up $L (i - 1, j)$ and diagonal $L (i - 1, j - 1)$ ). Nothing above row $i - 1$ is ever read again.

So keep just the previous row and the current row: two arrays of length $n + 1$ . You can even collapse to one row plus a single saved "diagonal" scalar.

$Space = O (min (m, n))$ (put the shorter string along the columns).

What you lose: the full table, hence the ability to traceback the actual LCS string. You only recover the length. For the string you need the full grid (or Hirschberg's divide-and-conquer, which restores $O (n)$ space and the string at $O (mn)$ time).

L5.2 (LCS vs Longest Common Substring on the same input) For $X =$ ABCBA, $Y =$ BCBAA, compute both: (a) the LCS length, and (b) the longest common substring (contiguous) length. Show the one rule that differs.

Recall Solution L5.2

(a) LCS — mismatch inherits $max (up, left)$ ; answer at the corner.

	B	C	B	A	A
""	0	0	0	0	0
A	0	0	0	1	1
B	1	1	1	1	1
C	1	2	2	2	2
B	1	2	3	3	3
A	1	2	3	4	4

LCS length = 4 (BCBA).

(b) Longest common substring — the one changed rule: on a mismatch reset to 0, and the answer is the maximum cell anywhere, not the corner.

	B	C	B	A	A
""	0	0	0	0	0
A	0	0	0	1	1
B	1	0	1	0	0
C	0	2	0	0	0
B	1	0	3	0	0
A	0	0	0	4	1

Max cell = 4 (BCBA — here it happens to appear contiguously in both, so both answers coincide at 4). The structural difference: LCS reads the corner and never resets; substring resets on mismatch and scans for the global max. See Longest Common Substring.

Recall One-line self-test before you leave

Match rule? ::: diagonal $+ 1$ Mismatch rule (LCS)? ::: $max (up, left)$ , never reset Deletions to align both to LCS? ::: $m + n - 2 L$ Space to get length only? ::: $O (min (m, n))$ (loses traceback)

Connections

Dynamic Programming — every exercise here is one 2-D table.
Edit Distance — L4.1's $m + n - 2 L$ is the deletion-only edit distance.
Longest Increasing Subsequence — L4.2 reduces LIS to LCS.
Longest Common Substring — L5.2's reset-to-0 contrast.
Diff Algorithm · Sequence Alignment — real-world LCS traceback.

Exercises — DP problems — Longest Common Subsequence (LCS)