Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them.
A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.
Example 1:
Input: str1 = "abac", str2 = "cab" Output: "cabac" Explanation: str1 = "abac" is a subsequence of "cabac" because we can delete the first "c". str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac". The answer provided is the shortest such string that satisfies these properties.
Example 2:
Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa" Output: "aaaaaaaa"
Constraints:
1 <= str1.length, str2.length <= 1000str1 and str2 consist of lowercase English letters.The Shortest Common Supersequence (SCS) of two strings is the shortest string that contains both strings as subsequences. A key insight is the strong relationship between SCS and the Longest Common Subsequence (LCS). If we know the LCS, we can merge the remaining characters from both strings while preserving order.
A common strategy is to first compute the LCS using Dynamic Programming. Build a DP table where dp[i][j] represents the length of the LCS for prefixes of the two strings. Once the table is filled, we can reconstruct the shortest supersequence by walking backward through the table and appending characters appropriately when they match or differ.
This approach ensures that common characters are not duplicated, keeping the resulting string minimal. The DP computation takes O(n × m) time, and reconstructing the supersequence also follows the same grid traversal with O(n × m) space usage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming using LCS table | O(n × m) | O(n × m) |
| Reconstructing the Shortest Common Supersequence | O(n + m) | O(n × m) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
We can find the length of the longest common subsequence between str1[i:] and str2[j:] (for all (i, j)) by using dynamic programming.
We can use this information to recover the shortest common supersequence.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of the Shortest Common Supersequence problem frequently appear in FAANG and other top tech interviews. It tests understanding of dynamic programming, string manipulation, and the relationship between LCS and SCS.
A 2D dynamic programming table is typically used to compute the LCS between the two strings. This table helps track overlapping subproblems and is later used to reconstruct the shortest common supersequence efficiently.
The optimal approach uses Dynamic Programming based on the Longest Common Subsequence (LCS). By first computing the LCS table, you can reconstruct the shortest supersequence by merging characters from both strings while avoiding duplicates.
The LCS represents characters common to both strings in order. By identifying this shared subsequence, we can avoid repeating those characters when building the supersequence, ensuring the final string remains as short as possible.