Shortest Common Supersequence

Statement

Given two strings, str1 and str2, find the length of the shortest string that has both the input strings as subsequences.

Note: A string $X$ is a subsequence of string $Y$ if deleting some number of characters from $Y$ results in the string $X$.

Let’s assume that we have two strings as follows:

• str1 = "yabc"
• str2 = "xabc"

There can be multiple strings that have str1 and str2 as subsequences, for example, "xyaabcc" and "xyabbc", but the shortest string that has these input strings as subsequences is "xyabc". Please note that the sequence of alphabets in the string can be altered.

Constraints:

• $1 \leq$ str1.length, str2.length $\leq 500$
• str1 and str2 consist of lowercase English letters.

Examples

Try it yourself

Implement your solution in the following playground.

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach

A naive approach is to try all the supersequences, one character at a time.

The two changing parameters in our recursive function are the two indices, i1 and i2 which are incremented based on the following two conditions:

• If the characters at i1 and i2 are a match, skip one character from both the sequences and make a recursive call for the remaining lengths.
• If the characters do not match, call the function