Lesson 8 of 16

Find a Common Subsequence

Suppose you want the longest sequence of characters shared by two documents while preserving order. A subsequence may skip characters but cannot reorder them. A substring, by contrast, must be contiguous.

AC is a subsequence of ABC, but not a substring because it skips B. The longest shared subsequence is called the LCS.

Use two positions as the state

Let dp[i][j] be the LCS length for the first i characters of one string and the first j of the other.

• If the final characters match, use them together: dp[i-1][j-1] + 1.
• Otherwise, compare omitting either final character: max(dp[i-1][j], dp[i][j-1]).
• If either string is empty, the length is zero.

a, b = "ABCD", "ACBD"
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        if a[i - 1] == b[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
print(dp[-1][-1])

The output is 3. Both ABD and ACD are possible answers. The code finds only the length. Recovering the actual characters requires tracing which earlier cells supplied the answer.

A small table-construction trap

Writing [[0] * width] * height makes the rows refer to the same list. Updating one can appear to update others. Create each row separately, as above. This is the sharing issue from arrays and references.

For string lengths n and m, the table has (n+1)(m+1) cells. Both time and space are O(nm). If only the length is needed, retaining the previous and current rows can reduce space.

Check your understanding

For ABC and AC, what are the LCS length and the longest common substring length?