Shortest Common Supersequence of Two Strings

Problem statement

Given two strings str1 and str2, return the shortest string (supersequence) that has both str1 and str2 as subsequences. If multiple answers exist, you may return any of them.

A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywhere from T) results in the string S.

Let’s look at the following example:

• We have two strings, str1 = apple and str2 = les. The SCS of both the strings will be apples as it contains both the strings as a subsequence.

• We have two strings, str1 = AGGTAB and str2 = GXTXAYB. The SCS of both the strings will be AGGXTXAYB as it contains both the strings as a subsequence.

Solution: Dynamic programming approach

This problem is somewhat close to Longest Common Subsequence. We will use the following approach to solve this problem:

• First, we will find the LCS of the two strings.
• Then, we will insert the non-LCS characters in the LCS found above in their original order.

Let us consider our previous example, str1 = AGGTAB and str2 = GXTXAYB. LCS of str1 and str2 is GTAB. Once we find LCS, we insert characters of both strings in order and we get AGXGTXAYB.

This problem is one of the most asked problems in coding interviews.

Let’s move to the implementation now.