Questions: Longest Common Subsequence (LCS) Problem

Question 1

A greedy algorithm for LCS matches the first common character it finds, then continues from that point in both strings. On strings A = 'ABCB' and B = 'BACB', it matches 'B' at position A[1] and B[0], then 'C' and 'B', finding LCS length 3. Could it have done better?

• A. No — greedy always finds the optimal LCS length
• B. No — length 3 is the true LCS length, but greedy may have been lucky; on other inputs it can fail
• C. Yes — the actual LCS is length 4, which greedy missed by committing to 'B' too early
• D. Yes — but only because the strings have repeated characters, where greedy always fails

Answer: (B)

In this case greedy happened to find the correct length, but the reasoning is wrong. On other inputs, an early greedy match can block a longer overall subsequence — there is no guarantee that grabbing the first match produces the globally optimal result. The problem is that locally optimal choices can prevent globally optimal solutions. LCS requires explicitly comparing the two alternatives when characters don't match (skip from A vs. skip from B) and tracking which gives a longer result. Only exhaustive DP comparison guarantees the true maximum.

Question 2

In the LCS DP table, dp[i][j] represents:

• A. Whether characters A[i] and B[j] match
• B. The length of the LCS of the entire strings A and B, computed by row i and column j
• C. The length of the LCS of the first i characters of A and the first j characters of B
• D. The number of characters skipped in A to reach position i in the LCS

Answer: (C)

dp[i][j] is defined as the LCS length for the prefix of A of length i (A[1..i]) and the prefix of B of length j (B[1..j]). This prefix-subproblem structure enables the recurrence: when characters match, you extend dp[i-1][j-1] by one; when they don't match, you take max(dp[i-1][j], dp[i][j-1]). The final answer dp[m][n] gives the LCS of the complete strings.

Question 3

The LCS of two strings is generally unique — there is exactly one longest common subsequence.

• T. True
• F. False

Answer: False

Multiple subsequences of the same maximum length can exist. For example, the LCS of 'ABAB' and 'BABA' has length 3, but both 'ABA' and 'BAB' are valid LCSs. The DP table gives the LCS length deterministically, but the backtracking step may encounter ties — positions where both 'skip from A' and 'skip from B' are equally optimal. Different tie-breaking choices produce different but equally valid LCS sequences.

Question 4

Every substring of a string is also a subsequence of that string, but not every subsequence is a substring.

• T. True
• F. False

Answer: True

A substring requires consecutive characters; a subsequence only requires characters to appear in the same relative order, with gaps allowed. Since consecutive characters trivially maintain order without gaps, every substring is a subsequence. But 'AC' is a subsequence of 'ABC' (skipping 'B') without being a substring. The LCS problem uses the more flexible subsequence definition — this is what makes it applicable to comparing files line-by-line in the Unix diff command, where matching lines need not be adjacent.

Question 5

Why doesn't a greedy approach work for the LCS problem, and what does dynamic programming enable that greedy cannot?

Model answer: Greedy matches characters left-to-right, committing to the first match it finds. This fails because an early match can 'use up' a character position in a way that prevents a longer overall subsequence. DP solves this by explicitly considering both alternatives when characters don't match — skip from A or skip from B — and recording the best result in the table. Because the table is filled bottom-up from all prefix subproblems, every possible alignment is implicitly considered and the optimum is guaranteed.

The formal property DP exploits is optimal substructure: the LCS of A[1..i] and B[1..j] can be built from LCSs of smaller prefixes. Once dp[i][j] is computed, it is provably optimal for that prefix pair and never needs to be re-examined. Greedy lacks this guarantee because it commits to a local choice without verifying it doesn't foreclose better global options.