Is Shortest Common Supersequence easy or hard?

LeetCode classifies Shortest Common Supersequence as a Hard problem because it requires understanding the relationship between LCS and SCS and implementing correct reconstruction logic from the DP table.

Shortest Common Supersequence Python/Java solution

Most implementations first compute the LCS DP matrix and then reconstruct the supersequence by traversing the table. Python and Java solutions follow the same logic: fill the DP table, then iterate backward or merge using the LCS to build the final string.

How to solve Shortest Common Supersequence in O(n)?

An O(n) solution is not possible for the general case because the algorithm must compare characters across both strings. The optimal method computes the Longest Common Subsequence using dynamic programming in O(m*n) time and then reconstructs the final supersequence.

Is Shortest Common Supersequence asked at Google/Amazon/Meta?

Shortest Common Supersequence is a classic dynamic programming problem frequently used in technical interviews. Variations of LCS and sequence merging problems have appeared in interviews at companies like Google, Amazon, and Meta to test DP fundamentals and string manipulation.

What is the best approach for Shortest Common Supersequence ?

The optimal approach uses dynamic programming to compute the Longest Common Subsequence (LCS) between the two strings. Once the LCS table is built, reconstruct the shortest common supersequence by merging both strings while avoiding duplicate LCS characters. This runs in O(m*n) time and O(m*n) space.

What data structure is used in Shortest Common Supersequence ?

The core data structure is a 2D dynamic programming table used to compute the Longest Common Subsequence. The table stores the LCS length for prefixes of both strings and guides reconstruction of the final supersequence.

What is the time complexity of Shortest Common Supersequence ?

The optimal solution runs in O(m*n) time where m and n are the lengths of the two strings. This complexity comes from building the dynamic programming table for the Longest Common Subsequence. Constructing the final supersequence takes an additional O(m+n) time.

Description Hints 2 Solution Video 26:47

1092. Shortest Common Supersequence

Hard62.4% acceptance5 companies

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 <= 1000
str1 and str2 consist of lowercase English letters.

Asked at 5 companies

Microsoft

Google Amazon Meta Bloomberg

Topics

Dynamic Programming String

Hints open one at a time

Hint 1

We can find the length of the longest common subsequence between str1[i:] and str2[j:] (for all (i, j)) by using dynamic programming.

Hint 2

We can use this information to recover the shortest common supersequence.

26:47

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution