Shortest Common Supersequence
Hard · Dynamic Programming · String · Dynamic Programming
Problem
Given two strings str1 and str2, return the shortest string that contains both of them as subsequences. If several strings have that minimum length, you may return any one of them.
A string t contains s as a subsequence if deleting some (possibly zero) characters of t leaves s.
Your answer is accepted when it has the minimum length and contains both strings as subsequences.
Examples
Input: str1 = "geek", str2 = "eke" Output: "gekek"
"gekek" has length 5, the minimum (4 + 3 minus a common subsequence of length 2): "geek" sits at positions 0, 1, 3, 4 and "eke" at 1, 2, 3. "geeke" would be accepted too.
Input: str1 = "ab", str2 = "ab" Output: "ab"
Identical strings are their own shortest supersequence.
Input: str1 = "abc", str2 = "xy" Output: "xyabc"
No letter can be shared, so all 5 letters are needed; any interleaving that keeps both orders is accepted.
Constraints
- 1 <= str1.length, str2.length <= 1000
- Both strings consist of lowercase English letters
Approaches
- Baseline: keep the actual strings in the table — time O(n · m · (n + m)), space O(n · m · (n + m))
Follow-up
Only the length needs no reconstruction: it is n + m - LCS. With three strings the LCS shortcut no longer applies, and the table gets a third dimension. The use cases ask both.
Related problems
Start free on Cariara · Coding problems · System design studio
