DSA problem
Shortest Common Supersequence
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.
The length of the shortest common supersequence (SCS) follows a clean identity: |SCS| = |str1| + |str2| - |LCS(str1, str2)|. Every character outside the LCS contributes one symbol; matches in the LCS are shared between both strings and contribute only one symbol total.
To reconstruct the SCS string itself, first build the LCS DP table dp[i][j] = LCS length of str1[0..i) and str2[0..j). Then walk backwards from dp[m][n] and reconstruct the supersequence character by character:
- If
str1[i-1] == str2[j-1]: this character is shared. Prepend it once and move diagonally to(i-1, j-1). - Else if
dp[i-1][j] > dp[i][j-1]: the LCS grew from above. Prependstr1[i-1]and move to(i-1, j). - Else: the LCS grew from the left. Prepend
str2[j-1]and move to(i, j-1).
When one index reaches 0, prepend the remainder of the other string. Time and space are both O(m * n).
Examples
str1 = "abac", str2 = "cab""cabac"str1 = "aaaaaaaa", str2 = "aaaaaaaa""aaaaaaaa"str1 = "abc", str2 = "def""abcdef"Constraints
- 1 <= str1.length, str2.length <= 1000
- str1 and str2 consist of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.