DP on Sequences: LCS, Edit Distance and LIS

Three classical DP problems act on sequences: the longest common subsequence (LCS) of two strings, the edit distance (Levenshtein distance) between two strings, and the longest increasing subsequence (LIS) of one sequence. Each fills a table whose state is a pair of prefixes (or a single prefix with an auxiliary structure), and each is a standard GATE dynamic-programming question.

This note states the recurrences, works a full LCS table with traceback, and records the $O(n^2)$ and $O(n \lg n)$ routes to LIS.

A subsequence preserves order but need not be contiguous. A substring (or subarray) is contiguous. LCS and LIS ask for subsequences. A string of length $m$ has $2^m$ subsequences (counting repeats), which is why brute force over subsequences is hopeless and DP is needed.

Longest common substring is different. Its state is "longest common suffix of $X[1..i]$ and $Y[1..j]$": $s[i,j] = s[i-1,j-1] + 1$ if $X[i] = Y[j]$, and $s[i,j] = 0$ otherwise. The answer is the maximum entry of the table, not the bottom-right entry. For ABCBDAB and BDCABA the longest common substring has length 2 (for example AB), while the LCS has length 4.

For strings $X[1..m]$ and $Y[1..n]$, the natural state is "answer for the prefixes $X[1..i]$ and $Y[1..j]$" with $0 \le i \le m$ and $0 \le j \le n$. That gives an $(m+1) \times (n+1)$ table. Base row and column correspond to an empty prefix.

Pseudocode uses 1-based arrays, <- for assignment and X[i] for the $i$-th character of $X$.

Time / space. $\Theta(mn)$ time and space. Length alone needs only the previous row: $O(\min(m,n))$ extra space. Reconstructing one LCS walks from $c[m,n]$ toward $c[0,0]$: on a match, collect $X[i]$ and step diagonally; reverse the collected characters before output; otherwise step to the neighbour of equal value.

Allowed operations: insert one character, delete one character, substitute one character (each cost 1). Let $d[i,j]$ be the edit distance of $X[1..i]$ and $Y[1..j]$.

(The three options are delete, insert and substitute.) Time $\Theta(mn)$. If substitute is forbidden, drop the diagonal option and force a delete-plus-insert of cost 2 when characters differ.

Link to LCS. With insertions and deletions only, the distance is exactly $m + n - 2\,\mathrm{LCS}(X,Y)$: keep a longest common subsequence, delete the other $m - \mathrm{LCS}$ characters of $X$ and insert the other $n - \mathrm{LCS}$ characters of $Y$.

Related material. LIS is not named separately in the GATE syllabus; it is included because it is the standard one-sequence DP companion of LCS.

$O(n^2)$ DP. Let $L[i]$ be the length of a longest increasing subsequence ending at index $i$. Then $L[i] = 1 + \max\{ L[j] : j < i,\ A[j] < A[i] \}$, or $1$ if no such $j$. Answer $\max_i L[i]$. Time $\Theta(n^2)$.

$O(n \lg n)$ patience method. Maintain an array tail[k] = smallest tail value of any increasing subsequence of length $k$ seen so far. For each $A[i]$, binary-search the first tail entry $\ge A[i]$ and replace it (or append). The length of tail is the LIS length. Time $O(n \lg n)$. Strict versus non-decreasing is controlled by using $<$ versus $\le$ in the search.

LCS of $A$ with a sorted copy of $A$ (duplicates removed, for a strictly increasing LIS) also yields LIS in $O(n^2)$ and makes the connection to LCS explicit (CLRS Exercise 15.4-5).

Any LCS of $X[1..i]$ and $Y[1..j]$ either ends with the matched pair $X[i] = Y[j]$ (and the rest is an LCS of the shorter prefixes) or omits $X[i]$ or omits $Y[j]$. Those three cases partition the possibilities and justify the recurrence (CLRS 3e, Section 15.4).

An optimal alignment of the two prefixes ends with a match/substitute of the last characters, a deletion of $X[i]$, or an insertion of $Y[j]$. Optimal substructure follows by the usual cut-and-paste argument; the table has $O(mn)$ overlapping states.

$X =$ A B C B D A B ($m = 7$), $Y =$ B D C A B A ($n = 6$).

The length table $c[i,j]$ (rows $X$, columns $Y$):

Length $c[7,6] = 4$. The backward traceback collects ABCB; reversing that buffer gives the LCS BCBA. Exactly three distinct strings are LCSs here: BCAB, BCBA and BDAB. A traceback that prefers "up" on ties and one that prefers "left" can return different strings; both are correct.

Distance 3. The DP table's bottom-right entry is 3. With insertions and deletions only, the distance becomes $6 + 7 - 2 \cdot 4 = 5$, since $\mathrm{LCS}(\text{KITTEN}, \text{SITTING}) = 4$ (ITTN).

Rows are prefixes of $X =$ ABC, columns are prefixes of $Y =$ YABD; the first row and column are the base cases $d[0,j] = j$ and $d[i,0] = i$.

$d[3,4] = 2$: insert Y in front, keep A and B, substitute C by D. Cell $d[1,2] = 1$ comes from the match A = A on the diagonal: $d[0,1] = 1$.

$O(n^2)$: lengths ending at each index are $1,2,1,3,2,4,4,5$. LIS length 5, for example $10,22,33,50,60$.

Patience method (replace the first tail entry $\ge$ the new value, else append):

The final size is 5, the LIS length. The final tail array is not itself an increasing subsequence of the input: 9, 21, 33, 41, 60 would need 33 to come after 21, but 33 appears earlier. Recovering an actual LIS needs predecessor pointers.

Edit distance equals the minimum cost of an alignment of the two strings, where a column is a matched or substituted pair, a deletion (character of $X$ against a gap), or an insertion (gap against a character of $Y$). The DP recurrence evaluates the best last column of any alignment of the two prefixes. This view makes the three-way $\min$ memorable: diagonal = substitute or match, up = delete, left = insert.

Common misconceptions.