Longest Common Subsequence (LCS): Build the DP Table Step by Step

A subsequence may skip characters, but it must preserve their order. That simple rule often gets lost when an LCS table appears as a grid of unexplained numbers. For X = AGGTAB and Y = GXTXAYB, the complete table yields GTAB, while the recurrence, complexity, variants, and traps explain how to solve an LCS without greedy guessing.

Subsequences and LCS: order matters, adjacency does not

A subsequence deletes zero or more elements without changing the retained order. In S = ABCDE, ACE uses positions 1, 3, and 5. BCD is both a substring and a subsequence. AEC is not, because it reverses the source order of E and C. A substring must use consecutive positions.

A length-five string has 2^5 = 32 index-selected subsequences, including the empty sequence, so 31 are non-empty. It has 5 x 6 / 2 = 15 non-empty substrings. Repeated characters can make different index choices display the same string, so 2^n need not count distinct values.

A common subsequence appears in both strings. An LCS has maximum length, but it need not be unique. Here the length is 4 and GTAB is one valid answer. The table proves both claims.

LCS recurrence: define the prefix state before filling the table

Define dp[i][j] as the LCS length of prefixes X[0..i-1] and Y[0..j-1]. An empty prefix has no non-empty common subsequence, so dp[0][j] = 0 and dp[i][0] = 0. Thus lengths m and n need a (m+1) x (n+1) table.

The transition depends on the last characters of the two prefixes:

• If X[i-1] = Y[j-1], then dp[i][j] = 1 + dp[i-1][j-1].

• Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

A match extends a best answer for shorter prefixes. On a mismatch, an optimum excludes at least one unequal last character, so diagonal plus one is wrong. Fill rows from i = 1..m and columns from j = 1..n; all dependencies are then ready. Dynamic Programming Explained: 0/1 Knapsack applies the same state-and-base-case discipline, though its recurrence differs.

LCS worked example: fill every cell for AGGTAB and GXTXAYB

Rows represent X = AGGTAB, with m = 6. Columns represent Y = GXTXAYB, with n = 7. Including empty prefixes produces this 7 by 8 table:

dp[1][1] = 0 because A != G. At dp[1][5], A = A, giving 1 + dp[0][4] = 1. Similarly, dp[2][1] = 1 + dp[1][0] = 1 for G, dp[4][3] = 1 + dp[3][2] = 2 for T, and dp[6][7] = 1 + dp[5][6] = 4 for B.

Mismatch cells carry the stronger neighbour. At dp[4][4], above is 1 and left is 2, so the value is 2. At dp[5][6], above is 2 and left is 3, so the value is 3. Therefore dp[6][7] gives LCS length 4.

LCS backtracking, time complexity and space trade-offs

Backtrack from (6,7). Match B, move diagonally to (5,6), then left to (5,5), where value 3 remains. Match A, move diagonally to (4,4), left to (4,3), and match T. At (3,2), choose up on the tie, move left from (2,2) to (2,1), and match G. Reverse B, A, T, G to get GTAB.

On a mismatch tie, either direction preserves the optimal length and may produce a different valid answer. Choosing up is only this trace's policy; it does not list every LCS.

Processing all m x n non-base cells takes O(mn) time and O(mn) full-table space. For length only, current and previous rows use O(min(m,n)) space when the shorter string is the column axis. Ordinary backtracking still needs the table or another reconstruction method. Sorting Algorithms: Complexity and Comparison is a revision bridge for asymptotic analysis, but LCS has two input lengths and its own O(mn) bound.

LCS variants and related reductions: know which recurrence changes

Longest common substring requires contiguity. For X = ABABC and Y = BABCA, it is BABC, length 4. Its DP resets mismatches to 0 and takes the maximum over all cells. LCS carries above or left and reads the bottom-right.

The main example also gives useful reductions:

• With only insertion and deletion allowed, keep the four LCS characters. Delete m - L = 6 - 4 = 2 characters and insert n - L = 7 - 4 = 3, for 2 + 3 = 5 operations. Equivalently, m + n - 2L = 6 + 7 - 8 = 5. This is not general edit distance because substitution is excluded.

• The shortest common supersequence length is m + n - L = 6 + 7 - 4 = 9.

• Longest palindromic subsequence reduces to LCS of a string and its reverse. For BBABCBCAB and BACBCBABB, the LCS length is 7, and BABCBAB is one valid palindromic subsequence.

Prefix-pair dependencies suit grid DP. Arbitrary graph paths need different states; Graph Algorithms: BFS, DFS and Shortest Paths covers that family.

LCS exam questions and common traps

Questions may ask for an LCS length, missing cells, recurrence, base cases, one reconstructed sequence, space complexity, or the subsequence-versus-substring distinction.

Use these checkpoints for quick recall:

1. dp[4][4] = 2.

2. The bottom-right value is 4.

3. Insertion plus deletion needs 5 operations.

4. The shortest common supersequence length is 9.

For a tie example, X = ABCBDAB and Y = BDCABA have LCS length 4. Both BCBA and BDAB are valid optimal answers, so “an LCS” need not be unique.

Common traps are direct: order matters but adjacency does not; mismatch uses max; the table stores lengths, not characters; earliest-match greed proves nothing; and dp[m][n] is only a length until backtracking. Two rolling rows do not preserve the ordinary path.

KnowledgeGate has over 20 LCS and subsequences questions available for practice. The GATE CS Exam Preparation category places that practice beside surrounding subject preparation.

Longest Common Subsequence in short and the next step

Define dp[i][j] on prefixes, initialise the empty row and column to zero, take diagonal plus one on a match, and take the maximum of above and left on a mismatch. Fill the table, read dp[m][n], then backtrack through matches. Here, dp[6][7] = 4 and one reconstructed answer is GTAB.

For active recall, redraw the AGGTAB by GXTXAYB table from the recurrence. Recompute dp[4][4] = 2 and dp[5][6] = 3, recover GTAB, and explain why (4,4) moves left rather than diagonally. Then solve the ABCBDAB and BDCABA tie case on paper. Once the trace is clear, use the GATE Test Series for topic-wise practice.