Shortest Common Supersequence

Construct the shortest string that contains two given strings as subsequences.

dynamic-programming strings lcs dp backtracking

Write a function `shortest_common_supersequence(str1: str, str2: str) -> str` that returns any string `s` such that:
- `str1` is a subsequence of `s`,
- `str2` is a subsequence of `s`,
- `s` has the minimum possible length among all such strings.
If multiple answers exist, return any one of them.

A subsequence is obtained by deleting zero or more characters from a string without changing the order of the remaining characters. The input strings consist of lowercase English letters. Both strings may be empty.

Your solution must run in O(n*m) time and O(n*m) space, where n = len(str1) and m = len(str2).

Constraints

0 ≤ len(str1), len(str2) ≤ 1000. The function must return a string. Your solution must be correct for all inputs within these bounds.

Example

>>> shortest_common_supersequence('abac', 'cab')
'cabac'
>>> shortest_common_supersequence('abc', 'ac')
'abc'
>>> shortest_common_supersequence('', 'xyz')
'xyz'
>>> shortest_common_supersequence('aaa', 'aaa')
'aaa'

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of the length of the shortest supersequence: it is len(str1) + len(str2) - len(LCS).

Build a DP table for the LCS length between prefixes, then walk backwards to reconstruct the supersequence.

When characters match, take that character once; otherwise, take the character from the side that gives the shorter remaining supersequence.

Handle the case where one string becomes empty by simply appending the rest of the other string.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.