# Shortest Common Supersequence

Let's solve the Shortest Common Supersequence problem using Dynamic Programming.

## Statement

Given two strings, `str1`

and `str2`

, find the length of the shortest string that has both the input strings as subsequences.

Note:A string $X$ is a subsequence of string $Y$ if deleting some number of characters from $Y$ results in the string $X$.

Let’s assume that we have two strings as follows:

`str1 = "yabc"`

`str2 = "xabc"`

There can be multiple strings that have `str1`

and `str2`

as subsequences, for example, `"xyaabcc"`

and `"xyabbc"`

, but the shortest string that has these input strings as subsequences is `"xyabc"`

. Please note that the sequence of alphabets in the string can be altered.

**Constraints:**

- $1 \leq$
`str1.length`

,`str2.length`

$\leq 3000$ `str1`

and`str2`

consist of lowercase English letters.

## Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.