What is the time complexity of Shortest Common Supersequence ?

The optimal solution has a time complexity of O(m*n).

What is the space complexity of Shortest Common Supersequence ?

The space complexity is O(m*n).

What data structures are used to solve Shortest Common Supersequence ?

This problem uses String, Dynamic Programming. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Shortest Common Supersequence ?

Insight 1: The length of the shortest common supersequence is the sum of the lengths of the two strings minus the length of their longest common subsequence (LCS). Insight 2: Dynamic programming can be used to efficiently find the length of the longest common subsequence and also to reconstruct the shortest common supersequence.

Which companies ask LeetCode 1092. Shortest Common Supersequence in interviews?

This problem is frequently asked at Dream11.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Shortest Common Supersequence - LeetCode 1092 Solution

Shortest Common Supersequence - Complete Solution Guide

Shortest Common Supersequence is LeetCode problem 1092, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 d

Detailed Explanation

The problem asks us to find the shortest string that contains both input strings, `str1` and `str2`, as subsequences. A subsequence is a sequence of characters that can be derived from another sequence by deleting some or no characters without changing the order of the remaining characters. The goal is to find the shortest possible string that fulfills this condition, and if multiple such strings exist, returning any one of them is acceptable. The inputs are two strings, `str1` and `str2`, consisting of lowercase English letters, with lengths between 1 and 1000.

Solution Approach

The solution uses dynamic programming to find the longest common subsequence (LCS) of the two input strings. The LCS is then used to construct the shortest common supersequence. The DP table `dp[i][j]` stores the length of the LCS of `str1[0...i-1]` and `str2[0...j-1]`. After building the DP table, we trace back from `dp[m][n]` to construct the supersequence. If `str1[i-1]` and `str2[j-1]` are equal, it means they are part of the LCS, so we add that character to our result and move diagonally up and to the left. If they are not equal, we compare `dp[i-1][j]` and `dp[i][j-1]` to see which way we came from. If `dp[i-1][j]` is greater, we add `str1[i-1]` to the result and move up. Otherwise, we add `str2[j-1]` to the result and move to the left. Once we have traced all the way back to either the top or the left edge of the DP table, we add any remaining characters from the other string to the result. Finally, we reverse the result to get the shortest common supersequence.

Step-by-Step Algorithm

Step 1: Initialize a 2D DP table `dp` of size `(m+1) x (n+1)` with all values set to 0, where `m` is the length of `str1` and `n` is the length of `str2`.
Step 2: Iterate through the DP table from `i = 1` to `m` and `j = 1` to `n`.
Step 3: If `str1[i-1]` is equal to `str2[j-1]`, then `dp[i][j] = 1 + dp[i-1][j-1]`. This means we've found a common character and we extend the LCS by 1.
Step 4: If `str1[i-1]` is not equal to `str2[j-1]`, then `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`. This means we take the maximum LCS length by either skipping a character from `str1` or skipping a character from `str2`.
Step 5: After filling the DP table, initialize an empty string `res` to store the shortest common supersequence.
Step 6: Initialize `i = m` and `j = n` to start from the bottom-right corner of the DP table.
Step 7: While `i > 0` and `j > 0`:
- If `str1[i-1]` is equal to `str2[j-1]`, append the character `str1[i-1]` to `res`, decrement `i` and `j`.
- Else if `dp[i-1][j] > dp[i][j-1]`, append the character `str1[i-1]` to `res`, decrement `i`.
- Else, append the character `str2[j-1]` to `res`, decrement `j`.
Step 8: While `i > 0`, append the character `str1[i-1]` to `res`, decrement `i`.
Step 9: While `j > 0`, append the character `str2[j-1]` to `res`, decrement `j`.
Step 10: Reverse the string `res` to obtain the shortest common supersequence.
Step 11: Return the string `res`.

Key Insights

Insight 1: The length of the shortest common supersequence is the sum of the lengths of the two strings minus the length of their longest common subsequence (LCS).
Insight 2: Dynamic programming can be used to efficiently find the length of the longest common subsequence and also to reconstruct the shortest common supersequence.
Insight 3: When reconstructing the supersequence, if characters at the current indices of `str1` and `str2` are equal, that character is part of the LCS and included in the supersequence once. Otherwise, we include the character from whichever string contributed to the longer LCS length at that point (or either if the LCS lengths are equal).

Complexity Analysis

Time Complexity: O(m*n)

Space Complexity: O(m*n)

Topics

This problem involves: String, Dynamic Programming.

Companies

Asked at: Dream11.

Shortest Common Supersequence | LeetCode 1092

Hard

String Dynamic Programming

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

Solution Code

Available in:

class Solution {
    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] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        StringBuilder res = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                res.append(str1.charAt(i - 1));
                i -= 1;
                j -= 1;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                res.append(str1.charAt(i - 1));
                i -= 1;
            } else {
                res.append(str2.charAt(j - 1));
                j -= 1;
            }
        }

        while (i > 0) {
            res.append(str1.charAt(i - 1));
            i -= 1;
        }
        while (j > 0) {
            res.append(str2.charAt(j - 1));
            j -= 1;
        }

        return res.reverse().toString();
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1092: Shortest Common Supersequence - Detailed explanation and solution approaches.

Topics

String Dynamic Programming

Companies

Dream11

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:1092

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

14 steps

1
Step 1: Initialize a 2D DP table `dp` of size `(m+1) x (n+1)` with all values set to 0, where `m` is the length of `str1` and `n` is the length of `str2`.
2
Step 2: Iterate through the DP table from `i = 1` to `m` and `j = 1` to `n`.
3
Step 3: If `str1[i-1]` is equal to `str2[j-1]`, then `dp[i][j] = 1 + dp[i-1][j-1]`. This means we've found a common character and we extend the LCS by 1.
4
Step 4: If `str1[i-1]` is not equal to `str2[j-1]`, then `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`. This means we take the maximum LCS length by either skipping a character from `str1` or skipping a character from `str2`.
5
Step 5: After filling the DP table, initialize an empty string `res` to store the shortest common supersequence.
6
Step 6: Initialize `i = m` and `j = n` to start from the bottom-right corner of the DP table.
7
Step 7: While `i > 0` and `j > 0`:
8
- If `str1[i-1]` is equal to `str2[j-1]`, append the character `str1[i-1]` to `res`, decrement `i` and `j`.
9
- Else if `dp[i-1][j] > dp[i][j-1]`, append the character `str1[i-1]` to `res`, decrement `i`.
10
- Else, append the character `str2[j-1]` to `res`, decrement `j`.
11
Step 8: While `i > 0`, append the character `str1[i-1]` to `res`, decrement `i`.
12
Step 9: While `j > 0`, append the character `str2[j-1]` to `res`, decrement `j`.
13
Step 10: Reverse the string `res` to obtain the shortest common supersequence.
14
Step 11: Return the string `res`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m*n)

💾

Space Complexity

O(m*n)

📝

Why?

The time complexity is determined by the nested loops required to compute the longest common subsequence using dynamic programming. We iterate over each cell in the m x n grid. The space complexity is determined by the size of the DP table, which is proportional to the product of the lengths of the input strings. The length of the final result string `res` depends on how many characters get concatenated and the length is bounded by O(m+n).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Recursive Approach with Memoization

A recursive approach can be implemented to calculate the length of LCS, and memoization can be used to avoid recomputation of overlapping subproblems. However, due to the potential for stack overflow with large inputs, iterative DP is generally preferred.

Time: O(m*n)Space: O(m*n) for memoization table + O(m+n) call stack space in worst case.

Trade-offs: Recursive with memoization is conceptually simpler to understand, but iterative DP is more robust due to the elimination of call stack limits.

✨

Key Insights

1Insight 1: The length of the shortest common supersequence is the sum of the lengths of the two strings minus the length of their longest common subsequence (LCS).
2Insight 2: Dynamic programming can be used to efficiently find the length of the longest common subsequence and also to reconstruct the shortest common supersequence.
3Insight 3: When reconstructing the supersequence, if characters at the current indices of `str1` and `str2` are equal, that character is part of the LCS and included in the supersequence once. Otherwise, we include the character from whichever string contributed to the longer LCS length at that point (or either if the LCS lengths are equal).

📚

Key Terms Explained

For Students

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: One of the strings is empty. In this case, the shortest common supersequence is simply the other string. The algorithm handles this correctly because the DP table correctly reflects that LCS is empty and the backtracking part ensures the remaining string is appended.
Edge case 2: The two strings are identical. In this case, the shortest common supersequence is just the string itself. The algorithm handles this case correctly because the DP table will reflect that the entire string is the LCS, and the reconstruction step will only include the characters once.
Edge case 3: Long string input. While theoretically feasible, the space complexity might be a concern with string lengths close to the constraint of 1000 characters. It might cause issues with memory limitations depending on available system resources.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the case where one of the strings is empty, which leads to incorrect results or runtime errors. The provided solution initializes the DP table such that `dp[i][0]` and `dp[0][j]` are 0.

✗Common mistake 2: Incorrectly reconstructing the shortest common supersequence. It's essential to correctly trace back through the DP table to build the supersequence string and reversing the final result to match the question requirement.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Bioinformatics - Aligning DNA sequences to find similarities and differences. The shortest common supersequence can be used to represent the combined sequence with minimal insertions or deletions.

🏦Real-world scenario 2: Text editing - Finding the minimal set of changes (insertions and deletions) needed to transform one document into another. This is the basis of many diff algorithms used in version control systems.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

String problems often involve sliding windows or two pointers. Consider if the character set is limited (lowercase letters = only 26 possibilities).

🎯 Interview Tip

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ Watch Out

Mutating strings directly in languages where strings are immutable. Use StringBuilder or arrays.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 13, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

❓

Frequently Asked Questions

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

How do I identify if a problem needs dynamic programming?

DP problems typically have: 1) Overlapping subproblems (same calculation repeated), 2) Optimal substructure (optimal solution uses optimal solutions to subproblems). Look for keywords like "minimum/maximum," "count ways," "is it possible," or "longest/shortest."

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Shortest Common Supersequence "?

For this hard-level String problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?