101
0/320
Loading content...
You are given two strings, str1 and str2, each consisting of lowercase English characters. Your task is to construct and return the shortest possible string that contains both str1 and str2 as subsequences.
A subsequence of a string is a new string that can be derived from the original string by deleting some (or no) characters without changing the relative order of the remaining characters. For instance, "ace" is a subsequence of "abcde", but "aec" is not.
The goal is to find the minimal-length string such that both input strings appear as subsequences within it. If multiple valid results of the same minimal length exist, you may return any one of them.
To visualize this problem, imagine you're trying to weave two threads together into a single rope. The characters of each original string must appear in order within the final rope, but you can interleave them and share common characters to minimize the total length.
For example, if one string is "abc" and another is "bcd", you don't need to create "abcbcd" (length 6). Instead, you can construct "abcd" (length 4) where:
The key insight is that characters common to both strings (in this case, "bc") can be shared, reducing the total length.
The challenge lies in determining the optimal way to merge the two strings:
str1 = "abac"
str2 = "cab""cabac"The string "cabac" has length 5 and contains both input strings as subsequences:
str1 = "aaaaaaaa"
str2 = "aaaaaaaa""aaaaaaaa"When both strings are identical, the shortest supersequence is the string itself. Any single instance of the string naturally contains itself as a subsequence.
str1 = "abc"
str2 = "def""abcdef"When the two strings have no common characters, the minimal supersequence is simply their concatenation. The output "abcdef" has length 6, which equals len(str1) + len(str2). Both strings appear as subsequences:
Constraints