#1092

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Shortest Common Supersequence

Compute the shortest string containing both given strings as subsequences using state transition dynamic programming efficiently.

string dynamic programming

Problem Statement

Given two strings str1 and str2, return the shortest string that contains both str1 and str2 as subsequences. A subsequence allows characters to be skipped but maintains relative order. If multiple valid shortest strings exist, return any one of them.

A string s is a subsequence of string t if s can be formed by deleting zero or more characters from t without changing the order of the remaining characters. For example, given str1 = "abac" and str2 = "cab", the shortest common supersequence is "cabac" because both strings appear as subsequences.

Examples

Example 1

Input: str1 = "abac", str2 = "cab"

Output: "cabac"

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"

Example details omitted.

Constraints

1 <= str1.length, str2.length <= 1000
str1 and str2 consist of lowercase English letters.

Solution Approach

Compute Longest Common Subsequence (LCS)

Use dynamic programming to build a 2D array dp where dp[i][j] represents the length of the LCS between str1[i:] and str2[j:]. This step identifies shared character sequences that guide the supersequence construction and ensures minimal repetition.

Reconstruct Supersequence Using LCS

Starting from dp[0][0], iterate through both strings. When characters match, append to the result and move diagonally in dp. When characters differ, choose the path leading to a longer LCS to append the correct character from str1 or str2, maintaining subsequence constraints.

Finalize and Return Result

After traversing both strings using the LCS map, append any remaining characters from str1 or str2. This guarantees the final string is the shortest possible while preserving both original sequences as subsequences.

Complexity Analysis

Metric	Value
Time	O(n \cdot m)
Space	O(n \cdot m)

Time complexity is O(n * m) due to filling the LCS dp table for all pairs of indices. Space complexity is also O(n * m) for storing the dp table. Optimizations like using two rows instead of full dp can reduce space to O(min(n, m)).

What Interviewers Usually Probe

Candidate recognizes dynamic programming structure for subsequences.
Candidate efficiently computes LCS before merging strings.
Candidate handles edge cases where one string is entirely a subsequence of the other.

Common Pitfalls or Variants

Common pitfalls

Not using LCS leads to longer than necessary supersequence.
Incorrectly merging characters may violate subsequence property.
Failing to append remaining unmatched characters at the end of reconstruction.

Follow-up variants

Return all possible shortest common supersequences.
Compute shortest common supersequence for more than two strings.
Modify problem to find supersequence minimizing a custom cost function.

FAQ

What is the shortest common supersequence problem?

It is the task of finding the minimal-length string containing two given strings as subsequences, preserving relative order.

How does dynamic programming apply to this problem?

We use state transition DP to compute the longest common subsequence, which guides the shortest supersequence construction.

Can multiple valid shortest common supersequences exist?

Yes, when multiple sequences share the same minimal length, any of them is acceptable as a solution.

What are common mistakes when solving Shortest Common Supersequence?

Failing to use LCS first, merging characters incorrectly, or not handling remaining characters at the end can produce invalid or longer results.

Is there a space optimization for this DP approach?

Yes, instead of storing the full dp table, two rows can be maintained to reduce space from O(n*m) to O(min(n,m)).

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m, n = len(str1), len(str2)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                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 = []
        i, j = m, n
        while i or j:
            if i == 0:
                j -= 1
                ans.append(str2[j])
            elif j == 0:
                i -= 1
                ans.append(str1[i])
            else:
                if f[i][j] == f[i - 1][j]:
                    i -= 1
                    ans.append(str1[i])
                elif f[i][j] == f[i][j - 1]:
                    j -= 1
                    ans.append(str2[j])
                else:
                    i, j = i - 1, j - 1
                    ans.append(str1[i])
        return ''.join(ans[::-1])

Continue Practicing

#1048 longest string chain #1143 longest common subsequence #1147 longest chunked palindrome decomposition