1092. Shortest Common Supersequence
Shortest Common Supersequence (LeetCode 1092) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Longest Common Subsequence - LCS) subpattern.
How to solve Shortest Common Supersequence
Shortest Common Supersequence is a Longest Common Subsequence problem, part of Dynamic Programming (DP) Patterns. Find longest common subsequence between two strings using 2D DP.
Work towards the solution in these steps:
- Consider using dynamic programming to systematically explore overlapping subproblems in the sequences.
- Recall how the Longest Common Subsequence (LCS) problem uses a 2D DP array to find common subsequences between two strings.
- Think about how the shortest common supersequence relates to the LCS; specifically, how the supersequence length connects to the LCS length.
The reference solution runs in O(m * n) time and O(m * n) space.
The Shortest Common Supersequence solution and editorial walks through the full approach with reference code.
Problem statement
Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If multiple answers exist, you may return any of them.
(A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywhere from T) 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.
Note: 1 <= str1.length, str2.length <= 1000 str1 and str2 consist of lowercase English letters.
Topics and companies
Topics: Dynamic Programming.
Reported in interviews at Microsoft, Amazon.
How to practise Shortest Common Supersequence on Thita.ai
Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(m * n) space.
Open Shortest Common Supersequence in the code editor, or read the Shortest Common Supersequence editorial for a worked solution with its approach and complexity analysis.
Where Shortest Common Supersequence sits in the DSA pattern sheet
- Dynamic Programming (DP) Patterns pattern guide
- 2D Array (Longest Common Subsequence - LCS) subpattern
- The full DSA patterns sheet
Problems related to Shortest Common Supersequence
Other problems that use the same 2D Array (Longest Common Subsequence - LCS) and Dynamic Programming (DP) Patterns techniques:
- Distinct Subsequences — Hard, same subpattern
- Longest Common Subsequence — Medium, same subpattern
- Minimum Insertion Steps to Make a String Palindrome — Hard, same subpattern
- Best Time to Buy and Sell Stock — Easy, same pattern
- Best Time to Buy and Sell Stock II — Medium, same pattern
- Best Time to Buy and Sell Stock III — Hard, same pattern
Shortest Common Supersequence FAQ
What is the LeetCode number of Shortest Common Supersequence?
Shortest Common Supersequence is LeetCode problem 1092, rated Hard.
What pattern is used to solve Shortest Common Supersequence?
Shortest Common Supersequence is a Longest Common Subsequence problem. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Longest Common Subsequence - LCS) subpattern.
What is the time complexity of Shortest Common Supersequence?
The reference solution runs in O(m * n) time and O(m * n) space.
Which companies ask Shortest Common Supersequence?
Shortest Common Supersequence has been reported in interviews at Microsoft, Amazon.