Find the shortest string that contains two given strings as subsequences.
Problem
Given two strings str1 and str2, return the shortest common supersequence (SCS) of the two strings.
A string is a supersequence of another string if it can be formed by inserting characters anywhere in the original string without changing the order of the existing characters.
Your task is to construct a string with minimum possible length such that both str1 and str2 are subsequences of it.
If there are multiple answers, you may return any one of them.
Notes
- A subsequence does not need to be contiguous.
- The answer should preserve the relative order of characters from both input strings.
- The shortest solution is typically built using dynamic programming over prefixes of the two strings.
Input Format
- Two strings
str1andstr2. - Each string consists of lowercase English letters.
Output Format
- Return one shortest common supersequence of
str1andstr2as a string.
Constraints
1 <= str1.length, str2.length <= 1000str1andstr2contain only lowercase English letters- If multiple shortest answers exist, return any one
Example 1
Input
str1 = "abac" str2 = "cab"
Output
"cabac"
Explanation
Both strings are subsequences of "cabac", and no shorter valid supersequence exists.
Example 2
Input
str1 = "geek" str2 = "eke"
Output
"geeke"
Explanation
"geeke" contains both "geek" and "eke" as subsequences and has minimum length.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.