# Interleaving Strings

Let's solve the Interleaving Strings problem using Dynamic Programming.

## Statement

Given strings `s1`

, `s2`

, and `s3`

, find whether an interleaving of `s1`

and `s2`

forms `s3`

.

An **interleaving** of two strings *a* and *b* is a configuration where *a* and *b* splits into $n$ and $m$ substrings, respectively, such that:

*a*$= a_{1}$ + $a_{2}$ + … + $a_{n}$*b*$= b_{1}$ + $b_{2}$ + … + $b_{m}$- $\left | n - m \right | \leqslant 1$
- The interleaving can follow either of the following two formats:
- $a_{1} + b_{1} + a_{2} + b_{2} + a_{3} + b_{3} + ...$
- $b_{1} + a_{1} + b_{2} + a_{2} + b_{3} + a_{3} + ...$

- $a_{x}$ can be a consecutive sequence of characters in string
`s1`

. - $b_{x}$ can be a consecutive sequence of characters in string
`s2`

.

Note:$a + b$ is the concatenation of the strings $a$ and $b$.

Let’s say we have two strings, “abc” and “xyz”. We may interleave them in multiple ways. We may alternately pick one character from each string until we have used up all the characters, giving us “axbycz” and “xaybzc”. Or, we may try to pick two characters at a time from each string, giving us “abxycz” and “xyabzc”. If we pick three characters at a time, we get “abcxyz” and “xyzabc”. Another class of variations is to pick a variable number of characters from each string, which leads to many more possibilities, such as “abxcyz”, “xayzbc”, and so on. However, “bxaycz” is *not* a valid interleaving, as the order of the characters taken from the first string is not preserved, since “b” appears here *before* “a”. Similarly, “acxybz” is *not* a valid interleaving.

**Constraints:**

- $0 \leq$
`s1.length`

,`s2.length`

$\leq 1500$ - $0 \leq$
`s3.length`

$\leq 3000$ `s1`

,`s2`

, and`s3`

consist of lowercase English letters.

## Examples

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