LCS and Subsequences Interview Questions with Worked Answers

Build an interview-ready explanation of longest common subsequence through one full DP trace, reconstruction, rolling rows, variants and edge cases.

KnowledgeGate Team

Exam prep & CS education

Updated 30 Oct 20266 min read
LCS and Subsequences Interview Questions with Worked Answers

Many candidates can recite the LCS recurrence but lose clarity when asked to define the state, fill the table, recover an actual subsequence or adapt the solution. The worked trace uses X = "ABCBDAB" and Y = "BDCABA", then connects the table to space optimisation, variants and edge cases. A strong answer explains the reasoning aloud, not merely a memorised code pattern.

What is a subsequence, and how is it different from a substring?

A subsequence preserves relative order, but its characters need not occupy adjacent positions. A substring occupies one contiguous interval. In S = "AXBYCZ", "ABC" is a subsequence using 1-based positions 1, 3, 5, but it is not a substring. "XBY" is a substring at positions 2-4, so it is also a subsequence.

The empty string and the full string are both subsequences. A length-n string has 2^n position-selected subsequences, including the empty one. Thus, "ABCA" has 2^4 = 16 selections. These are not necessarily 16 distinct strings because repeated letters can make different selections produce the same text.

Recognition cue: two strings, preserved order and permitted skips suggest LCS. Consecutive characters suggest longest common substring.

How do you define the LCS state and recurrence?

Let X = "ABCBDAB", with m = 7, and Y = "BDCABA", with n = 6. Define dp[i][j] as the LCS length of prefixes X[1..i] and Y[1..j]. Set dp[0][j] = 0 and dp[i][0] = 0 because an empty prefix has no non-empty common subsequence.

The transition is:

  • If X[i] == Y[j], then dp[i][j] = 1 + dp[i-1][j-1]. The matching final character extends an optimal answer for both shorter prefixes.

  • Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]). At least one unmatched final character must be excluded.

Top-down memoisation and bottom-up tabulation both visit at most m x n = 7 x 6 = 42 non-base states here, so both take O(mn) time. The same state-transition discipline appears in Dynamic Programming Explained with a Worked 0/1 Knapsack, although knapsack uses a different recurrence.

Can you fill the table and recover one actual LCS?

X prefix / Y prefix

empty

B

D

C

A

B

A

empty

0

0

0

0

0

0

0

A

0

0

0

0

1

1

1

B (first)

0

1

1

1

1

2

2

C

0

1

1

2

2

2

2

B (second)

0

1

1

2

2

3

3

D

0

1

2

2

2

3

3

A (second)

0

1

2

2

3

3

4

B (final)

0

1

2

2

3

4

4

Therefore, dp[7][6] = 4.

For reconstruction, use this deterministic tie rule: when upper and left are equal, move up. From (7,6), move up to (6,6) on the 4/4 tie. Match A and go diagonally to (5,5). Move up to (4,5) because 3 > 2, then match B. Move left to (3,3) because 2 > 1, then match C. Move left to (2,1) because 1 > 0, then match B.

Backtracking collects A, B, C, B in reverse, giving "BCBA". The length is fixed, but the sequence need not be unique. "BCBA", "BCAB" and "BDAB" are all length-4 common subsequences here. Without a supplied tie rule, an implementation may return any of them.

Dynamic programming table for X = ABCBDAB and Y = BDCABA, with orange arrows tracing a backtrack to BCBA and highlighting the final length 4.

Can you reduce the space, and what do you lose?

Tabulation computes 42 non-base states in O(mn) time and stores (m+1)(n+1) = 8 x 7 = 56 values in O(mn) space. If only the length is required, keep two rows and use the shorter string for the columns. Space falls to O(min(m,n)), while time remains O(mn).

With Y = "BDCABA" as the columns, the row after processing "ABCBDA" is [0,1,2,2,3,3,4]. After the final B, it becomes [0,1,2,2,3,4,4]. At Y's second B, calculate 1 + previous[4] = 1 + 3 = 4. At the final A, calculate max(left 4, up 4) = 4.

These arrays retain the final length but cannot reconstruct a sequence alone. Use the full table, parent pointers or an advanced method if asked.

Two-row LCS update for X = ABCBDAB and Y = BDCABA, comparing 56 full-table values with 14 rolling-row values and final length 4.

How do common LCS follow-ups change the answer?

Prompt

What changes

Worked result

Longest common substring

On a match, use 1 + diagonal. On a mismatch, reset the local cell to 0. Track the maximum over all cells.

For "ABABC" and "BABCA", the maximum is 4 for "BABC". Ordinary LCS would retain max(up, left) on a mismatch.

Shortest common supersequence

Reuse the LCS length: m + n - LCS.

For "AGGTAB" and "GXTXAYB", LCS is "GTAB", length 4, so 6 + 7 - 4 = 9. "AGGXTXAYB" is one valid length-9 supersequence containing both inputs in order.

Minimum insertions and deletions

Keep the LCS, delete unmatched source characters and insert unmatched target characters.

For "heap" to "pea", LCS is "ea", length 2. The count is 4 + 3 - 2 x 2 = 3: delete h, delete the final p, then insert p at the front.

The last formula counts insertions and deletions only. It does not treat substitution as one edit.

Which mistakes and edge cases expose a memorised solution?

  • Matching greedily -> scanning X = "ABCBDAB" left to right and taking the earliest possible match in Y = "BDCABA" can produce "ABA", length 3, while the optimum is 4. DP avoids a locally early match blocking a better suffix.

  • Treating LCS as longest common substring -> retain the better prefix result on a mismatch instead of resetting to zero.

  • Returning only 4 when a sequence was requested -> backtrack and return one valid LCS.

  • Claiming "BCBA" is unique -> remember that "BCAB" and "BDAB" are also valid.

  • Moving diagonally on a mismatch -> move toward the larger neighbouring value. State a deterministic tie rule if a judge expects one answer.

Test ("", "ABC") -> 0, ""; ("AAAA", "AA") -> 2, "AA"; ("ABC", "DEF") -> 0, ""; and ("ABC", "ABC") -> 3, "ABC".

How should you present the answer and handle interviewer follow-ups?

Use a spoken-answer ladder:

  1. Clarify whether the output is the length, one sequence or all sequences.

  2. Define dp[i][j], then state the bases and recurrence.

  3. Give O(mn) time and the space appropriate to the requested output.

  4. Dry-run one matching cell and one mismatching cell.

  5. Test empty, duplicate and no-match inputs.

For all LCS strings, the output can be large, so O(mn) cannot describe complete enumeration. DSA Interview Questions: 7 Patterns for Placements broadens this into pattern recognition. Coding Round Strategy: Triage, Time-Box, Bank Marks helps decide whether to code full reconstruction under time pressure. Coding & Skills is the wider catalogue route.

For additional practice, use the Algorithm > Dynamic Programming > LCS & Subsequences lesson and sort attempts into definition, table-trace and variant questions.

Short version and the next practice step

  • state = two prefixes

  • match -> 1 + diagonal

  • mismatch -> max(up, left)

  • answer for the running input = 4

  • one reconstructed LCS = BCBA

Rebuild the final two rows and explain why BCAB is also valid without looking back. For an optional structured route, continue with DSA using Java. For broader coding practice, use Coding for Placements.