# Shortest Common Supersequence 
**Difficulty:** HARD
[External](https://leetcode.com/problems/shortest-common-supersequence)
Canonical: https://scaleengineer.com/dsa/problems/shortest-common-supersequence
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Dream11](https://scaleengineer.com/companies/dream11)
---
## 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 <= 1000`
* `str1` and `str2` consist of lowercase English letters.

# Approaches
## Recursive Approach (Brute Force)
This approach uses a straightforward recursive method to solve the problem. It breaks down the problem into smaller subproblems by considering the first characters of the two strings. While simple to conceptualize, it suffers from massive performance issues due to re-calculating solutions for the same pairs of substrings multiple times.
**Time:** O(2^(m+n)). In the worst-case scenario (when no characters match), each recursive call branches into two, leading to an exponential number of calls. · **Space:** O(m + n), where m and n are the lengths of the strings. This is due to the recursion depth and the storage of strings in each recursive call.
**Pros:** Simple to understand and directly follows the problem's recursive definition.; Easy to implement without complex data structures.
**Cons:** Extremely inefficient due to a large number of redundant computations for the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest inputs due to its exponential time complexity.
### Explanation
The core idea is to build the shortest common supersequence (SCS) character by character from the beginning. At each step, we compare the first characters of the current substrings of `str1` and `str2`.

If the characters match, we know this character must be in the SCS. We add it to our result and proceed to find the SCS for the remaining parts of both strings.

If the characters do not match, we have a choice. We can either take the character from `str1` and find the SCS for the rest of `str1` and the entirety of `str2`, or we can take the character from `str2` and find the SCS for `str1` and the rest of `str2`. To ensure the final supersequence is the shortest, we recursively explore both paths and choose the one that yields a shorter result.

This method naturally leads to a recursive structure but creates an explosion of function calls for the same subproblems, making it impractical for the given constraints.

```java
// Note: This solution is for demonstration and will Time Limit Exceed.
class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        // Base case: if one string is empty, the other is the SCS.
        if (str1.isEmpty()) {
            return str2;
        }
        if (str2.isEmpty()) {
            return str1;
        }

        // If first characters are the same, they contribute one char to SCS.
        if (str1.charAt(0) == str2.charAt(0)) {
            return str1.charAt(0) + shortestCommonSupersequence(str1.substring(1), str2.substring(1));
        } else {
            // If different, explore two paths and choose the shorter result.
            String res1 = str1.charAt(0) + shortestCommonSupersequence(str1.substring(1), str2);
            String res2 = str2.charAt(0) + shortestCommonSupersequence(str1, str2.substring(1));
            
            if (res1.length() < res2.length()) {
                return res1;
            } else {
                return res2;
            }
        }
    }
}
```
### Algorithm
- Define a recursive function, say `solve(s1, s2)`, that takes two strings and returns their shortest common supersequence.
- **Base Case**: If either string is empty, the SCS is simply the other non-empty string. Return it.
- **Recursive Step**:
  - If the first characters of `s1` and `s2` are the same (`s1[0] == s2[0]`): The common character can be used once. The result is this character prepended to the result of the recursive call on the rest of the strings: `s1[0] + solve(s1.substring(1), s2.substring(1))`. 
  - If the first characters are different: We have two possibilities to form the supersequence.
    1. Include `s1[0]` in the supersequence and find the SCS of the rest of `s1` and all of `s2`. Result: `s1[0] + solve(s1.substring(1), s2)`.
    2. Include `s2[0]` in the supersequence and find the SCS of all of `s1` and the rest of `s2`. Result: `s2[0] + solve(s1, s2.substring(1))`. 
  - Compare the lengths of the two resulting strings from the above step and return the shorter one.

## Dynamic Programming (LCS-based)
This optimal approach uses dynamic programming. The key insight is that the shortest common supersequence is formed by taking all characters from both strings but counting the characters of their longest common subsequence (LCS) only once. The algorithm first computes the lengths of LCS for all prefixes of the strings and stores them in a DP table. Then, it backtracks through this table to construct the SCS string.
**Time:** O(m * n), where m and n are the lengths of the input strings. The dominant operation is filling the DP table. · **Space:** O(m * n) to store the 2D DP table required for backtracking.
**Pros:** Guaranteed to find the optimal solution.; Efficient for the given constraints with a polynomial time complexity.
**Cons:** Requires extra space proportional to the product of the lengths of the two strings.
### Explanation
The problem of finding the shortest common supersequence is closely related to finding the longest common subsequence. The length of the SCS is given by `len(str1) + len(str2) - len(LCS(str1, str2))`. While we can compute the LCS string first, a more direct method is to use the DP table generated during the LCS length calculation to build the SCS.

First, we populate a `dp[m+1][n+1]` table where `dp[i][j]` stores the length of the LCS between `str1[0...i-1]` and `str2[0...j-1]`. This takes O(m*n) time.

Next, we reconstruct the SCS. We start from the end of both strings (`i=m`, `j=n`) and build the SCS string backwards. 
- If `str1[i-1]` and `str2[j-1]` are the same, this character is part of the LCS. We add it once to our result and move to consider the prefixes `str1[0...i-2]` and `str2[0...j-2]`.
- If they are different, we must include both characters in the SCS eventually. We look at our `dp` table to decide which one to add now. The one that is *not* on the path to the longer LCS of the subproblems is added. For example, if `dp[i-1][j]` (LCS of `str1` prefix and `str2` full) is greater than `dp[i][j-1]`, it means `str1[i-1]` is unique at this step and must be added. We then move to the subproblem that gave the longer LCS.

This process continues until we've processed both strings completely. The resulting string is built in reverse, so a final reversal is needed.

```java
class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        
        // Step 1: Fill DP table for LCS lengths
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                } else 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]);
                }
            }
        }
        
        // Step 2: Backtrack to build the SCS string
        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--;
            }
        }
        
        // Append remaining characters from str1 or str2
        while (i > 0) {
            scs.append(str1.charAt(i - 1));
            i--;
        }
        while (j > 0) {
            scs.append(str2.charAt(j - 1));
            j--;
        }
        
        return scs.reverse().toString();
    }
}
```
### Algorithm
- **Step 1: Compute the Longest Common Subsequence (LCS) DP Table.**
  - Create a 2D array `dp` of size `(m+1) x (n+1)`, where `m = str1.length()` and `n = str2.length()`.
  - `dp[i][j]` will store the length of the LCS of `str1.substring(0, i)` and `str2.substring(0, j)`.
  - Fill the table using the standard LCS recurrence relation:
    - If `str1[i-1] == str2[j-1]`, then `dp[i][j] = 1 + dp[i-1][j-1]`.
    - Otherwise, `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`.

- **Step 2: Construct the SCS by Backtracking.**
  - Initialize two pointers, `i = m` and `j = n`, and an empty `StringBuilder` for the result.
  - Traverse the `dp` table backwards from `dp[m][n]`:
    - If `str1[i-1] == str2[j-1]`: This character is common. Append it to the result, and move diagonally up-left (`i--`, `j--`).
    - If `str1[i-1] != str2[j-1]`: The characters are different. We must include both, but not at the same time. We check the `dp` table to see which character was excluded to form the LCS at the previous step.
      - If `dp[i-1][j] > dp[i][j-1]`, it means the path to the LCS came from `dp[i-1][j]`. So, `str1[i-1]` is a non-common character that must be in the SCS. Append `str1[i-1]` and move up (`i--`).
      - Otherwise, the path came from `dp[i][j-1]`. Append the non-common character `str2[j-1]` and move left (`j--`).
  - After the loop, one of the pointers might still be greater than 0. Append the remaining part of the corresponding string.
  - Finally, reverse the constructed string to get the correct SCS.

# Solutions
### Java

```java
class Solution {
public
  String shortestCommonSupersequence(String str1, String str2) {
    int m = str1.length(), n = str2.length();
    int[][] f = 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)) {
          f[i][j] = f[i - 1][j - 1] + 1;
        } else {
          f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
        }
      }
    }
    int i = m, j = n;
    StringBuilder ans = new StringBuilder();
    while (i > 0 || j > 0) {
      if (i == 0) {
        ans.append(str2.charAt(--j));
      } else if (j == 0) {
        ans.append(str1.charAt(--i));
      } else {
        if (f[i][j] == f[i - 1][j]) {
          ans.append(str1.charAt(--i));
        } else if (f[i][j] == f[i][j - 1]) {
          ans.append(str2.charAt(--j));
        } else {
          ans.append(str1.charAt(--i));
          --j;
        }
      }
    }
    return ans.reverse().toString();
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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])

```