How do you solve Shortest Common Supersequence on LeetCode?

Shortest Common Supersequence (LeetCode #1092) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(m * n) time complexity and O(m * n) space complexity. Key insight: Finding the longest common subsequence helps in minimizing the length of the supersequence.

What is the time complexity of Shortest Common Supersequence ?

The optimal solution for Shortest Common Supersequence runs in O(m * n) time and uses O(m * n) space. The time complexity is O(m * n) due to the nested loops used to fill the DP table, where m and n are the lengths of str1 and str2 respectively.

What is the brute force solution for Shortest Common Supersequence ?

The brute force approach for Shortest Common Supersequence is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves generating all possible combinations of characters from both strings and checking if they are subsequences of both. This is straightforward but inefficient, as it explores many unnecessary combinations. The optimal Optimal Solution approach improves this to O(m * n).

What algorithm or data structure is used to solve Shortest Common Supersequence ?

Shortest Common Supersequence uses the following concepts: String, Dynamic Programming. The recommended patterns to study are: Dynamic Programming, Two Pointers.

What are the interview tips for Shortest Common Supersequence ?

Explain your thought process clearly while coding. Be prepared to discuss the trade-offs of different approaches. Practice writing out the DP table for similar problems to become comfortable with the concept.

What are common mistakes when solving Shortest Common Supersequence ?

Not understanding the difference between subsequence and substring. Failing to correctly backtrack through the DP table to construct the final result.

#1092

Shortest Common Supersequence

Hard

StringDynamic ProgrammingDynamic ProgrammingTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(m * n)
Space	O(1)	O(m * n)

💡

Intuition

Time O(m * n)Space O(m * n)

The optimal solution uses dynamic programming to find the longest common subsequence (LCS) first. The shortest common supersequence can then be constructed using the LCS to minimize the length while ensuring both strings are subsequences.

⚙️

Algorithm

3 steps

1Step 1: Create a DP table to find the length of the longest common subsequence between str1 and str2.
2Step 2: Use the DP table to backtrack and construct the shortest common supersequence.
3Step 3: Append characters from both strings while skipping the common characters found in the LCS.

solution.py36 lines

1# Full working Python code
2
3def shortest_common_supersequence(str1, str2):
4    m, n = len(str1), len(str2)
5    dp = [[0] * (n + 1) for _ in range(m + 1)]
6
7    for i in range(1, m + 1):
8        for j in range(1, n + 1):
9            if str1[i - 1] == str2[j - 1]:
10                dp[i][j] = dp[i - 1][j - 1] + 1
11            else:
12                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
13
14    i, j = m, n
15    result = []
16
17    while i > 0 and j > 0:
18        if str1[i - 1] == str2[j - 1]:
19            result.append(str1[i - 1])
20            i -= 1
21            j -= 1
22        elif dp[i - 1][j] > dp[i][j - 1]:
23            result.append(str1[i - 1])
24            i -= 1
25        else:
26            result.append(str2[j - 1])
27            j -= 1
28
29    while i > 0:
30        result.append(str1[i - 1])
31        i -= 1
32    while j > 0:
33        result.append(str2[j - 1])
34        j -= 1
35
36    return ''.join(result[::-1])

ℹ

Complexity note: The time complexity is O(m * n) due to the nested loops used to fill the DP table, where m and n are the lengths of str1 and str2 respectively.

1Finding the longest common subsequence helps in minimizing the length of the supersequence.
2Dynamic programming is a powerful technique for solving problems involving sequences.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.