> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Shortest Common Supersequence Python Solution

> Tested Python solution for LeetCode 1092 with 14 pytest cases. Generate a practice environment with lcpy.

LeetCode 1092, [Hard](/catalog/hard). Topics: [String](/catalog/topics/string), [Dynamic Programming](/catalog/topics/dynamic-programming). [View on LeetCode](https://leetcode.com/problems/shortest-common-supersequence/description/).

Generate this problem as a practice environment: tested reference solution, 14 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1092   # by problem number
lcpy gen -s shortest_common_supersequence   # by problem name
```

## Problem

Given two strings \<code>str1\</code> and \<code>str2\</code>, return \<em>the shortest string that has both \</em>\<code>str1\</code>\<em> and \</em>\<code>str2\</code>\<em> as \<strong>subsequences\</strong>\</em>. If there are multiple valid strings, return \<strong>any\</strong> of them.

A string \<code>s\</code> is a \<strong>subsequence\</strong> of string \<code>t\</code> if deleting some number of characters from \<code>t\</code> (possibly \<code>0\</code>) results in the string \<code>s\</code>.

### Examples

```
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.
```

```
Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"
Output: "aaaaaaaa"
```

### Constraints

* \<code>1 \<= str1.length, str2.length \<= 1000\</code>
* \<code>str1\</code> and \<code>str2\</code> consist of lowercase English letters.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/shortest_common_supersequence/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/shortest_common_supersequence/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(m * n)
    # Space: O(m * n)
    def shortest_common_supersequence(self, str1: str, str2: str) -> str:
        m, n = len(str1), len(str2)
        dp = [[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]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        out: list[str] = []
        i, j = m, n
        while i > 0 and j > 0:
            if str1[i - 1] == str2[j - 1]:
                out.append(str1[i - 1])
                i -= 1
                j -= 1
            elif dp[i - 1][j] >= dp[i][j - 1]:
                out.append(str1[i - 1])
                i -= 1
            else:
                out.append(str2[j - 1])
                j -= 1
        out.extend(str1[:i][::-1])
        out.extend(str2[:j][::-1])
        return "".join(reversed(out))
```

## Complexity

| Time | Space |
| - | - |
| O(m \* n) | O(m \* n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.