Build a Shortest Supersequence
Problem
Given two strings a and b, return a shortest string that contains both of them as subsequences, meaning each can be read from it left to right by skipping some characters. Several strings may share the shortest length; any one of them is accepted, and the examples show one. Either input may be empty.
Examples
Input: a = "tile", b = "style"
Output: "stiyle"
Why: length 6 = 4 + 5 - 3, since "tle" is shared and written onceInput: a = "abac", b = "cab"
Output: "cabac"
Why: "ab" is shared, so 4 + 3 - 2 = 5 characters are enoughInput: a = "", b = "xyz"
Output: "xyz"
Why: edge case, only b has to fitHints
0 / 3
Every character of a and b must appear, but a character both strings need at the same point can be written once for both. The more you share, the shorter the result.
The characters you can share are exactly a common subsequence, so the shortest length is len(a) + len(b) minus the longest common subsequence. The DP table tells you how long; you still need to read the string itself back from it.
Fill a table of longest common subsequence lengths for every pair of suffixes. Then walk from the start of both strings: on equal characters write one copy and advance both, otherwise write the character from the side whose skip keeps the larger table value and advance only that side. Append whatever is left of either string.
Solution
A supersequence that shares a common subsequence has length len(a) + len(b) minus the shared part, so the shortest one is built around a longest common subsequence. Cell i, j of the table holds the longest common subsequence length of a from i and b from j, which makes a forward walk possible. At each step the walk follows the cell that produced the current value: a match is written once, otherwise the character on the side that keeps the larger value is written and that side advances. Every character is written exactly once except the shared ones, which gives the optimal length. Time and space are both O(len(a) × len(b)).
def shortest_super(a, b):
m, n = len(a), len(b)
L = [[0] * (n + 1) for _ in range(m + 1)] # LCS of a[i:] and b[j:]
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
L[i][j] = L[i + 1][j + 1] + 1 if a[i] == b[j] else max(L[i + 1][j], L[i][j + 1])
out, i, j = [], 0, 0
while i < m and j < n: # read the answer back from the table
if a[i] == b[j]:
out.append(a[i]); i += 1; j += 1 # shared: written once
elif L[i + 1][j] >= L[i][j + 1]:
out.append(a[i]); i += 1 # a's character goes first
else:
out.append(b[j]); j += 1
return "".join(out) + a[i:] + b[j:] # one side may have leftovers
print(shortest_super("tile", "style")) # -> stiyle
print(shortest_super("abac", "cab")) # -> cabac
print(shortest_super("", "xyz")) # -> xyzStuck on the idea rather than the code? Reading the Answer Back covers it.