We need to build the shortest possible string that contains both str1 and str2 as subsequences. The task is to merge the two strings while preserving the relative order of characters from each, using as few total characters as possible.

Concatenating the two strings gives a valid supersequence of length m + n, but we can do better. Characters that appear in both strings, in a consistent order, only need to appear once in the result. So the problem reduces to finding the longest common subsequence (LCS) of the two strings, then arranging the remaining characters around it.

If the LCS has length L, the shortest common supersequence has length m + n - L. Each of the L shared characters is written once instead of twice, and every non-shared character is written exactly once.

Key Constraints:

Intuition

Build the supersequence by merging the two strings character by character and explore every way to do it. With two pointers i and j tracking positions in str1 and str2, each step takes the next character from str1, the next character from str2, or, when those two characters match, takes one copy that advances both pointers.

When the current characters match, taking one shared copy is always at least as good as taking either separately, so there is no need to branch in that case. When they differ, we try both options and keep whichever recursion returns the shorter string. Exploring every branch this way guarantees we find a shortest supersequence, but the work grows exponentially.

Algorithm

Visualization and Code

This becomes too slow once the strings exceed about 15 characters, because the same subproblem (i, j) is recomputed many times across different branches. The next approach removes that redundancy with dynamic programming, building the answer from a table instead of re-deriving it.

Intuition

The shortest common supersequence is built directly from the Longest Common Subsequence (LCS). A character that appears in the LCS only needs to appear once in the supersequence, because that single copy satisfies both str1 and str2 at the same time. Every other character appears once on its own. That makes the length m + n - LCS_length.

We need the actual string, not just its length. Build the standard LCS DP table, then trace back through it to construct the supersequence one character at a time. When the two current characters match (a diagonal move in the table), include that character once. When they differ, follow the direction that the DP table grew from, up or left, and include the corresponding character.

Algorithm

Visualization and Code

The next approach reaches the same answer in two separate phases: first recover the LCS string, then merge both inputs around it. The complexity is identical, but the two steps can be reasoned about independently.

Intuition

This approach separates the two concerns. First find the actual LCS string, not just its length. Then use the LCS as a skeleton and merge both input strings around it. For each LCS character, include all characters from str1 and str2 that come before it (the non-shared characters), then include the LCS character once.

The result matches Approach 2. The advantage is that the LCS recovery and the merge are independent steps, each short enough to verify on its own.

Algorithm

Visualization and Code