Shortest Common Supersequence - Solution & Explanation
Problem Statement
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 <= 1000str1andstr2consist of lowercase English letters.
Approach Overview
Problem Overview: Given two strings str1 and str2, construct the shortest string that contains both as subsequences. Characters must keep their original order from each string, but you can interleave them.
Approach 1: Dynamic Programming with LCS Reconstruction (O(m*n) time, O(m*n) space)
The shortest common supersequence (SCS) is closely related to the longest common subsequence (LCS). First compute the LCS table using classic dynamic programming. The LCS captures characters shared by both strings in order. Once the DP table is built, reconstruct the supersequence by walking backward from dp[m][n]. When characters match, append it once and move diagonally. When they differ, move toward the larger DP value and append the corresponding character. This guarantees the result keeps both strings as subsequences while avoiding duplicate shared characters.
This approach works because the optimal SCS length equals m + n - LCS. The DP table gives the structure needed to merge both strings efficiently. Time complexity is O(m*n) for building the LCS table, and reconstruction takes O(m+n). Space complexity is O(m*n) for the DP matrix.
Approach 2: Iterative Greedy Merge Using LCS (O(m*n) time, O(m*n) space)
Another implementation computes the LCS first, then performs a greedy merge of both strings while iterating through the LCS characters. Maintain two pointers for str1 and str2. For each LCS character, append all characters from str1 until reaching that character, then append all characters from str2 until reaching it. Finally append the shared LCS character once and advance both pointers. After processing all LCS characters, append remaining characters from both strings.
This method emphasizes string merging rather than backtracking through the DP table. It is often easier to implement when the LCS sequence is already available. The time complexity remains O(m*n) for computing the LCS and O(m+n) for the merge. Space complexity is O(m*n) for the DP used to compute LCS.
The problem heavily relies on understanding subsequence relationships in string problems and applying optimal substructure from dynamic programming.
Recommended for interviews: The dynamic programming LCS approach is the expected solution. Interviewers want to see that you recognize the SCS–LCS relationship and reconstruct the answer from the DP table. The greedy merge approach is a clean follow-up implementation once the LCS is known.
Approach 1: Dynamic Programming to Find LCS
This approach involves creating a dynamic programming table to calculate the Longest Common Subsequence (LCS) between the two strings. The shortest common supersequence will be constructed based on the LCS. We iterate through both strings and build a table where each cell represents the length of the LCS of the substrings up to given indices. After filling the table, we backtrack from the bottom-right cell to find the LCS, which helps in forming the shortest common supersequence by adding remaining characters from both strings.
In this Python implementation, we first compute the LCS using a dynamic programming table. Starting from the bottom-right corner, we backtrack to build the shortest common supersequence (SCS) by comparing characters in str1 and str2. Each matched character in both strings appends to the SCS, and unmatched characters are appended based on the higher value in the DP table, ensuring the constructed SCS is minimal.
Complexity
Time Complexity: O(m * n), where m and n are the lengths of str1 and str2. This is due to filling the DP table.
Space Complexity: O(m * n) for the DP table.
Approach 2: Iterative Greedy Approach
This approach leverages a two-pointer strategy to iterate through both strings simultaneously. We will construct the shortest common supersequence by greedily adding characters while moving through str1 and str2 step by step. This method emphasizes adding each character when they mismatch and consolidating the sequence when they match.
This C implementation uses two indices to traverse both strings. As the iteration proceeds, characters from str1 and str2 are added to the result array unless they match, in which case, the common character is added once. This greedy manner yields the shortest common supersequence.
Code
C
JavaScript
Complexity
Time Complexity: O(m + n) where m and n are the lengths of str1 and str2. We iterate across both strings once.
Space Complexity: O(m + n) for storing the result string.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming to Find LCS | Time Complexity: |
| Iterative Greedy Approach | Time Complexity: |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with LCS Reconstruction | O(m*n) | O(m*n) | Standard interview solution when reconstructing the supersequence directly from the DP table |
| Iterative Greedy Merge Using LCS | O(m*n) | O(m*n) | When the LCS string is already computed and you want a cleaner merge-based construction |
Video Solution
Shortest Common Supersequence | Dynamic Programming | Leetcode #1092 • Techdose • 28,149 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Shortest Common Supersequence easy or hard?
Shortest Common Supersequence Python/Java solution
How to solve Shortest Common Supersequence in O(n)?
Is Shortest Common Supersequence asked at Google/Amazon/Meta?
What is the best approach for Shortest Common Supersequence ?
What data structure is used in Shortest Common Supersequence ?
What is the time complexity of Shortest Common Supersequence ?
Ready to solve this problem?
Practice Shortest Common Supersequence with our built-in code editor and test cases.
Practice on FleetCode