Shortest Common Supersequence solution and explanation
Google
9 more videos on this problem
Shortest Common Supersequence | Dynamic Programming | Leetcode #1092Techdose · 26:47 · 28K views
Print Shortest Common Supersequence | DP On Strings | Leetcode 1092 | DP Concepts & Qns-21codestorywithMIK · 26:36 · 14K views
Shortest Common Supersequence - Leetcode 1092 - PythonNeetCodeIO · 30:16 · 12K views
花花酱 LeetCode 1092. Shortest Common Supersequence 刷题找工作 EP251Hua Hua · 13:18 · 3K views
Shortest Common Supersequence | Leetcode 1092Techdose · 29:24 · 3K views
1092. Shortest Common Supersequence | leetcode daily challenge | dsa | dp | faang | shashcodeShashCode · 12:36 · 2K views
1092. Shortest Common Supersequence | Recursion - Greedy - Memo - Bottom UpAryan Mittal · 15:41 · 1K views
1092. Shortest Common Supersequence (Leetcode Hard)Programming Live with Larry · 28:03 · 1K views
Daily Leetcode #1795: Feb 28, 2025 - 1092. Shortest Common SupersequenceProgramming Live with Larry · 23:26 · 516 views
LeetCode 1092 Shortest Common Supersequence | Dynamic Programming | LCS | Asked in Google MetaCode Harmony · 21:49 · 180 views
The problem
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.
def shortestCommonSupersequence(str1, str2):
m, n = len(str1), len(str2)
# Create DP table to store lengths of LCS
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Fill dp array
for i in range(m):
for j in range(n):
if str1[i] == str2[j]:
dp[i + 1][j + 1] = dp[i][j] + 1
else:
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
# Backtrack to find the shortest common supersequence
i, j = m, n
scs = []
while i > 0 and j > 0:
if str1[i - 1] == str2[j - 1]:
scs.append(str1[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
scs.append(str1[i - 1])
i -= 1
else:
scs.append(str2[j - 1])
j -= 1
while i > 0:
scs.append(str1[i - 1])
i -= 1
while j > 0:
scs.append(str2[j - 1])
j -= 1
return ''.join(reversed(scs))public class SCS {
public String shortestCommonSupersequence(String str1, String str2) {
int m = str1.length();
int n = str2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
StringBuilder scs = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
scs.append(str1.charAt(i - 1));
i--;
j--;
} else if (dp[i - 1][j] >= dp[i][j - 1]) {
scs.append(str1.charAt(i - 1));
i--;
} else {
scs.append(str2.charAt(j - 1));
j--;
}
}
while (i > 0) scs.append(str1.charAt(--i));
while (j > 0) scs.append(str2.charAt(--j));
return scs.reverse().toString();
}
}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.
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.
function shortestCommonSupersequence(str1, str2) {
let i = 0, j = 0;
const m = str1.length, n = str2.length;
let result = '';
while (i < m && j < n) {
if (str1[i] === str2[j]) {
result += str1[i];
i += 1;
j += 1;
} else if (i < m) {
result += str1[i++];
} else if (j < n) {
result += str2[j++];
}
}
result += str1.slice(i) + str2.slice(j);
return result;
}#include <stdio.h>
#include <string.h>
char* shortestCommonSupersequence(char *str1, char *str2) {
int m = strlen(str1), n = strlen(str2);
int i = 0, j = 0;
char result[2001]; // max possible length
int k = 0;
while (i < m && j < n) {
if (str1[i] == str2[j]) {
result[k++] = str1[i];
i++;
j++;
} else if (i < m) {
result[k++] = str1[i++];
} else if (j < n) {
result[k++] = str2[j++];
}
}
while (i < m) result[k++] = str1[i++];
while (j < n) result[k++] = str2[j++];
result[k] = '\0';
return strdup(result);
}This JavaScript solution employs a two-pointer technique iterating through str1 and str2. Characters in each string are compared and appended to the result in a manner optimized to minimize supersequence length, efficiently achieved via concatenation of the remaining substring parts.
Time Complexity: O(m + n), due to linear traversal over both strings.
Space Complexity: O(m + n) for the result storage.
Approach 3: Default Approach
class Solution {
public:
string shortestCommonSupersequence(string str1, string str2) {
int m = str1.size(), n = str2.size();
vector<vector<int>> f(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (str1[i - 1] == str2[j - 1])
f[i][j] = f[i - 1][j - 1] + 1;
else
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
}
}
int i = m, j = n;
string ans;
while (i || j) {
if (i == 0)
ans += str2[--j];
else if (j == 0)
ans += str1[--i];
else {
if (f[i][j] == f[i - 1][j])
ans += str1[--i];
else if (f[i][j] == f[i][j - 1])
ans += str2[--j];
else
ans += str1[--i], --j;
}
}
reverse(ans.begin(), ans.end());
return ans;
}
};function shortestCommonSupersequence(str1: string, str2: string): string {
const m = str1.length;
const n = str2.length;
const f = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
if (str1[i - 1] == str2[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1;
} else {
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
}
}
}
let ans: string[] = [];
let i = m;
let j = n;
while (i > 0 || j > 0) {
if (i === 0) {
ans.push(str2[--j]);
} else if (j === 0) {
ans.push(str1[--i]);
} else {
if (f[i][j] === f[i - 1][j]) {
ans.push(str1[--i]);
} else if (f[i][j] === f[i][j - 1]) {
ans.push(str2[--j]);
} else {
ans.push(str1[--i]);
--j;
}
}
}
return ans.reverse().join('');
}func shortestCommonSupersequence(str1 string, str2 string) string {
m, n := len(str1), len(str2)
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if str1[i-1] == str2[j-1] {
f[i][j] = f[i-1][j-1] + 1
} else {
f[i][j] = max(f[i-1][j], f[i][j-1])
}
}
}
ans := []byte{}
i, j := m, n
for i > 0 || j > 0 {
if i == 0 {
j--
ans = append(ans, str2[j])
} else if j == 0 {
i--
ans = append(ans, str1[i])
} else {
if f[i][j] == f[i-1][j] {
i--
ans = append(ans, str1[i])
} else if f[i][j] == f[i][j-1] {
j--
ans = append(ans, str2[j])
} else {
i, j = i-1, j-1
ans = append(ans, str1[i])
}
}
}
for i, j = 0, len(ans)-1; i < j; i, j = i+1, j-1 {
ans[i], ans[j] = ans[j], ans[i]
}
return string(ans)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming to Find LCS | Time Complexity: |
| Iterative Greedy Approach | Time Complexity: |
| Default Approach | – |
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 |
Frequently asked questions
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.