Longest Common Subsequence

Subsequences vs Substrings

A subsequence of a string is formed by deleting zero or more characters without changing the relative order of the remaining characters. Unlike a common substring, characters in a common subsequence do not need to appear contiguously in either input text.

Prefix Dynamic Programming Recurrence

For strings X of length m and Y of length n, let L[i, j] denote the LCS length of prefixes X[1..i] and Y[1..j]. Boundary cells satisfy L[i, 0] = 0 and L[0, j] = 0. For i ≥ 1 and j ≥ 1, if X[i] = Y[j] then L[i, j] = L[i - 1, j - 1] + 1; otherwise L[i, j] = max(L[i - 1, j], L[i, j - 1]). When multiple longest common subsequences achieve length L[m, n], selecting the ASCII-lexicographically smallest string yields a canonical witness.

Worked Example

Let us trace the Longest Common Subsequence computation for X = AABC and Y = ABAC:

1. Initialize a 5x5 table L with zeros in row 0 and column 0.
2. For i = 1, j = 1: X[1] = A matches Y[1] = A, so L[1, 1] = L[0, 0] + 1 = 1.
3. For i = 1, j = 2: X[1] = A does not match Y[2] = B, so L[1, 2] = max(L[0, 2], L[1, 1]) = max(0, 1) = 1.
4. Filling the remaining rows in row-major order yields L[4, 4] = 3.
5. Reconstructing the optimal subsequences of length 3 produces the unique witness AAC.

Experiment

Observe how the prefix dynamic programming table fills and breaks ties in https://riano.app/module/longest-common-subsequence:

1. Enter First text ABAB and Second text BABA.
2. Click Step repeatedly to watch cells reveal in row-major order while final length and witness remain Pending.
3. Click Finish to complete all 16 non-boundary cells and observe LCS length 3 with ASCII-smallest witness ABA (chosen over BAB).
4. Clear First text to empty and verify that an empty string is immediately terminal with LCS length 0 and witness Empty string.

Limitations

Full table storage requires O(m · n) time and O(m · n) space, and enumerating all tied optimal subsequences can grow exponentially when many alternating ties exist. This module bounds inputs to 0..8 characters from A..D so the entire DP grid and exact lexicographic witness remain clear.

Common Pitfalls

Do not confuse longest common subsequence with longest contiguous substring, or follow only a single greedy backtrack arrow (such as always moving up on ties) when an ASCII-lexicographically smallest witness is required across all optimal paths.

References

The recursive substructure and dynamic programming tabulation for Longest Common Subsequence follow standard computer science texts:

• Princeton Introduction to Programming in Java: Section 2.3 Recursion and Dynamic Programming