Longest Common Subsequence: Building the DP Table You Can Explain

Longest Common Subsequence (LCS) asks for the length of the longest sequence of characters that appears in both strings in order, but not necessarily contiguously.

Define dp[i][j] as the LCS length of the first i characters of text1 and the first j characters of text2. If text1[i-1] == text2[j-1], then dp[i][j] = dp[i-1][j-1] + 1. Otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Row 0 and column 0 are zero.

This is O(m*n) time and space. Because each row depends only on the previous row, you can keep two rows (or one row plus a saved diagonal value) and get O(min(m, n)) space, which is a common follow-up.

To reconstruct the actual subsequence, walk back from dp[m][n]: move diagonally when the characters match, otherwise step toward the larger neighbor. You need the full table for this, so mention that the space optimization only works when the length alone is required.

LCS is the parent of several problems: Shortest Common Supersequence (m + n - LCS), Delete Operation for Two Strings (m + n - 2*LCS), and a cousin of Edit Distance. Pointing out these connections shows pattern recognition.

When you explain it, start with the recurrence in words, fill a tiny 3x3 table by hand, and only then write the code.

Disclosure: I work on Linkjob AI. If you want to practice explaining problems like this out loud, the AI help for online coding assessments can help during mock sessions.