DSA Recovering the Actual LCS
Recovering the actual LCS means spelling out one longest common subsequence by walking a finished table backwards. The walk starts at the bottom right cell and collects matched characters in reverse.
The problem
Recovering the actual LCS means spelling out one longest common subsequence, not just its length. A common subsequence is a sequence of characters that appears in both strings in the same order.
The input is two strings. The output is one string. That string must be a subsequence of both inputs, and no longer common subsequence may exist.
The cases used in this article
cases = [
("stone", "longest", "one"),
("abcde", "ace", "ace"),
("bridge", "fridge", "ridge"),
("abc", "def", ""),
]
for a, b, expected in cases:
print(a, "vs", b, "->", repr(expected))The last row answers with the empty string. The two inputs share no character. An empty answer is still a correct answer there.
Intuition: the length alone does not spell anything
A finished length table reports a number. The number says how long the answer is. It says nothing about which characters form it.
A tempting shortcut scans the first string and keeps each character that appears anywhere in the second. That keeps characters in the wrong relative order. The kept string need not be a subsequence of the second string at all.
Keeping shared letters in the wrong order
a = "abc"
b = "cba"
kept = "".join(ch for ch in a if ch in b)
print("kept:", repr(kept))
def is_subseq(sub, word):
pos = 0
for ch in word:
if pos < len(sub) and ch == sub[pos]:
pos += 1
return pos == len(sub)
print("kept is a subsequence of b:", is_subseq(kept, b))
print("longest possible length here: 1")The kept string has length three. It is not a subsequence of the second string. Only the backward walk through the table recovers a string with a guarantee.
Brute force: test every subsequence and keep the longest shared ones
The brute force lists every subsequence of the first string. It tests each one against the second string. It keeps the longest ones that pass both tests.
Listing all of them also shows a second fact. More than one longest answer can exist. Any correct method returns just one of them.
The brute force, counted
def is_subseq(sub, word):
pos = 0
for ch in word:
if pos < len(sub) and ch == sub[pos]:
pos += 1
return pos == len(sub)
def all_longest(a, b):
best = []
tested = 0
for mask in range(2 ** len(a)):
sub = "".join(a[i] for i in range(len(a)) if mask >> i & 1)
tested += 1
if is_subseq(sub, b):
if not best or len(sub) > len(best[0]):
best = [sub]
elif len(sub) == len(best[0]) and sub not in best:
best.append(sub)
return sorted(best), tested
for a, b in [("abcde", "ace"), ("ab", "ba")]:
best, tested = all_longest(a, b)
print(a, "vs", b, "-> longest:", best, "tested:", tested)The short pair ab and ba has two longest answers. Both have length one. A method that returns either one is correct.
The optimal solution: walk the finished table backwards
The state is the finished prefix table from the length lesson. The walk starts at the bottom right cell and collects matched characters in reverse.
A matched cell adds its character and moves diagonally up and left. An unmatched cell moves toward the larger neighbour. Ties move up, and that fixed rule picks one fixed answer among equals.
The backward walk on every case
def lcs_table(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 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])
return dp
def recover(a, b, dp):
i, j = len(a), len(b)
out = []
while i > 0 and j > 0:
if a[i - 1] == b[j - 1]:
out.append(a[i - 1])
i, j = i - 1, j - 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
return "".join(reversed(out))
def is_subseq(sub, word):
pos = 0
for ch in word:
if pos < len(sub) and ch == sub[pos]:
pos += 1
return pos == len(sub)
cases = [
("stone", "longest", "one"),
("abcde", "ace", "ace"),
("bridge", "fridge", "ridge"),
("abc", "def", ""),
]
for a, b, expected in cases:
dp = lcs_table(a, b)
found = recover(a, b, dp)
ok = found == expected and len(found) == dp[len(a)][len(b)] and is_subseq(found, a) and is_subseq(found, b)
print(a, "vs", b, "->", repr(found), "expected:", repr(expected), "checks pass:", ok)Every case passes four checks at once. The string matches the expected answer. Its length equals the table corner. It is a subsequence of each input.
Walkthrough: recovering ace from abcde and ace
The walk starts where both strings are complete. The current characters there are e and e. They match, so e joins the collection and the walk steps diagonally.
A mismatch follows, and the walk moves up without collecting. Then c matches and joins the collection. One more mismatch moves up, then a matches, and the walk reaches the border.
The walk, step by step
def lcs_table(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 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])
return dp
a, b = "abcde", "ace"
dp = lcs_table(a, b)
i, j = len(a), len(b)
found = []
while i > 0 and j > 0:
if a[i - 1] == b[j - 1]:
print("cell", i, j, "- match on", repr(a[i - 1]), "- collect it")
found.append(a[i - 1])
i, j = i - 1, j - 1
elif dp[i - 1][j] >= dp[i][j - 1]:
print("cell", i, j, "- mismatch - move up")
i -= 1
else:
print("cell", i, j, "- mismatch - move left")
j -= 1
print("collected backwards:", found)
print("reversed once:", repr("".join(reversed(found))))The collection comes out backwards. One reversal at the end restores the reading order. Reversing during the walk would scramble it again.
Complexity
Building the table costs one step per pair of prefixes, so its time is O(m times n) for string lengths m and n. The walk then takes at most m plus n steps.
The table stores every cell, so its space is O(m times n). The walk needs the full table, because any cell on its path may guide the next move.
Brute tests against table cells
for n in [5, 10, 20]:
print("length", n, "- brute subsequences:", 2 ** n, " table cells:", n * n, " walk steps at most:", 2 * n)The brute force pays the exponential term in full. The walk adds only a short tail of work after the table. Recovery is nearly free once the lengths exist.
Edge cases and pitfalls
Forgetting the final reversal is the classic defect. The answer then reads backwards. A palindrome answer hides that defect, so tests need a non-palindrome case.
A tie between the top and left neighbours is not an error. Both moves stay on a longest path. The fixed tie rule only decides which longest answer comes out.
Edge cases, run
def lcs_table(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 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])
return dp
def recover(a, b, dp):
i, j = len(a), len(b)
out = []
while i > 0 and j > 0:
if a[i - 1] == b[j - 1]:
out.append(a[i - 1])
i, j = i - 1, j - 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
return "".join(reversed(out))
for a, b in [("", "abc"), ("abc", ""), ("abc", "abc"), ("ab", "ba"), ("abc", "def")]:
dp = lcs_table(a, b)
print(repr(a), "vs", repr(b), "->", repr(recover(a, b, dp)))The tie case returns the letter a. The brute force showed that b is equally valid. A test that demands one specific tied answer is testing the tie rule, not correctness.
Exercise
During the backward walk, the current characters match. What happens?