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

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], thendp[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.

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.

How do common LCS follow-ups change the answer?
Prompt | What changes | Worked result |
|---|---|---|
Longest common substring | On a match, use | For |
Shortest common supersequence | Reuse the LCS length: | For |
Minimum insertions and deletions | Keep the LCS, delete unmatched source characters and insert unmatched target characters. | For |
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 inY = "BDCABA"can produce"ABA", length3, while the optimum is4. 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
4when 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:
Clarify whether the output is the length, one sequence or all sequences.
Define
dp[i][j], then state the bases and recurrence.Give
O(mn)time and the space appropriate to the requested output.Dry-run one matching cell and one mismatching cell.
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 prefixesmatch -> 1 + diagonalmismatch -> max(up, left)answer for the running input = 4one 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.
Keep learning
Longest Common Subsequence (LCS): Build the DP Table Step by Step
Build an LCS table from its prefix state, trace every important cell, and backtrack one valid answer. The worked example ends with GTAB.
LCS & Subsequences MCQs: 12 Solved Questions with Explanations
Solve 12 LCS and subsequence questions drawn from GATE, UGC NET and concept practice. Each answer shows the DP or sequence reasoning you need.
Array Basics Interview Questions and Answers in C: Worked Traces and Traps
Build interview-ready answers for C arrays through exact memory, reversal, and second-largest traces, with the edge cases and reasoning behind each result.
Agent Architecture and Program Types Interview Questions: Model Answers with a Worked Design
Prepare crisp answers on agent functions, programs, architectures and agent types. Then follow a complete service-recovery design from percepts to a utility-based choice.





