Reconstruct a Longest Common Subsequence

01 · Question

Given strings a and b, return one longest common subsequence. A subsequence preserves order but may skip characters. Return the empty string if none exists; any longest answer is acceptable. Treat characters as Unicode code points, not grapheme clusters.

Example: a="abcde", b="ace" returns "ace".

02 · Analysis

dp[i][j] is the LCS length of suffixes a[i:] and b[j:]. Equal characters can be matched, giving 1+dp[i+1][j+1]; otherwise skip either character and take the larger child. Fill backward from empty suffixes. Reconstruct forward: emit equal characters, otherwise follow a child preserving the optimum. Tie-breaking by advancing i returns one valid optimum. For n,m code points, time and table space are O(nm); reconstruction adds O(n+m) time and O(min(n,m)) output. Go explicitly converts to runes so indices have the same meaning as Python.

03 · Solution

Reference solution

1def longest_common_subsequence(a, b):
2    n, m = len(a), len(b)
3    dp = [[0] * (m + 1) for _ in range(n + 1)]
4    for i in range(n - 1, -1, -1):
5        for j in range(m - 1, -1, -1):
6            if a[i] == b[j]:
7                dp[i][j] = 1 + dp[i+1][j+1]
8            else:
9                dp[i][j] = max(dp[i+1][j], dp[i][j+1])
10    result = []
11    i = j = 0
12    while i < n and j < m:
13        if a[i] == b[j]:
14            result.append(a[i])
15            i += 1
16            j += 1
17        elif dp[i+1][j] >= dp[i][j+1]:
18            i += 1
19        else:
20            j += 1
21    return ''.join(result)

0/1 Subset Sum