# LeetCode 97: Interleaving String

## Problem Restatement

We are given three strings:

```python
s1: str
s2: str
s3: str
```

We need to decide whether `s3` can be formed by interleaving `s1` and `s2`.

Interleaving means we take all characters from `s1` and all characters from `s2`, while preserving the original order inside each string.

The characters may be mixed together.

For example:

```python
s1 = "abc"
s2 = "def"
```

A valid interleaving is:

```python
"adbcef"
```

because the characters from `s1` still appear as:

```python
a -> b -> c
```

and the characters from `s2` still appear as:

```python
d -> e -> f
```

The official problem asks whether `s3` is formed by an interleaving of `s1` and `s2`. The examples include `s1 = "aabcc"`, `s2 = "dbbca"`, `s3 = "aadbbcbcac"` returning `true`, and `s3 = "aadbbbaccc"` returning `false`. The constraints allow `s1.length` and `s2.length` up to `100`, and `s3.length` up to `200`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Strings `s1`, `s2`, and `s3` |
| Output | `True` if `s3` is an interleaving, otherwise `False` |
| Order rule for `s1` | Characters from `s1` must appear in original order |
| Order rule for `s2` | Characters from `s2` must appear in original order |
| Length rule | `len(s1) + len(s2)` must equal `len(s3)` |

Function shape:

```python
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        ...
```

## Examples

Example 1:

```python
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"
```

This is valid.

One way to read `s3` is:

```python
aa      from s1
dbbc    from s2
bc      from s1
a       from s2
c       from s1
```

The order inside `s1` is preserved.

The order inside `s2` is preserved.

Answer:

```python
True
```

Example 2:

```python
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbbaccc"
```

This cannot be formed while preserving both source orders.

Answer:

```python
False
```

Example 3:

```python
s1 = ""
s2 = ""
s3 = ""
```

Both source strings are empty.

The target is also empty.

Answer:

```python
True
```

## First Thought: Recursion

At any point while building `s3`, we may take the next character from `s1` or the next character from `s2`.

Suppose we have already used:

```python
i characters from s1
j characters from s2
```

Then the next position in `s3` is:

```python
i + j
```

There are at most two choices:

1. If `s1[i] == s3[i + j]`, take the next character from `s1`.
2. If `s2[j] == s3[i + j]`, take the next character from `s2`.

A direct recursion follows this idea, but it repeats the same states many times.

So we use dynamic programming.

## Key Insight

Define:

```python
dp[i][j]
```

to mean:

```python
s3[:i + j] can be formed by interleaving s1[:i] and s2[:j]
```

So:

| State | Meaning |
|---|---|
| `i` | Number of characters taken from `s1` |
| `j` | Number of characters taken from `s2` |
| `i + j` | Number of characters formed in `s3` |

The answer is:

```python
dp[len(s1)][len(s2)]
```

## Length Check

Before doing DP, check the total length.

```python
if len(s1) + len(s2) != len(s3):
    return False
```

If the lengths do not match, `s3` cannot use exactly all characters from `s1` and `s2`.

## Transition

For state `dp[i][j]`, the last character of `s3[:i + j]` came from either `s1` or `s2`.

### Case 1: Last Character Came From `s1`

This is possible if:

```python
i > 0
```

and:

```python
s1[i - 1] == s3[i + j - 1]
```

Then we need the previous state:

```python
dp[i - 1][j]
```

So:

```python
dp[i][j] = dp[i][j] or dp[i - 1][j]
```

### Case 2: Last Character Came From `s2`

This is possible if:

```python
j > 0
```

and:

```python
s2[j - 1] == s3[i + j - 1]
```

Then we need the previous state:

```python
dp[i][j - 1]
```

So:

```python
dp[i][j] = dp[i][j] or dp[i][j - 1]
```

## Algorithm

Let:

```python
m = len(s1)
n = len(s2)
```

Create:

```python
dp = [[False] * (n + 1) for _ in range(m + 1)]
```

Set:

```python
dp[0][0] = True
```

Then fill the table.

For every `i` from `0` to `m`, and every `j` from `0` to `n`:

1. If the next state can come from `s1`, use `dp[i - 1][j]`.
2. If the next state can come from `s2`, use `dp[i][j - 1]`.

Return:

```python
dp[m][n]
```

## Walkthrough

Use:

```python
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"
```

Start:

```python
dp[0][0] = True
```

The first character of `s3` is `"a"`.

It can only come from `s1[0]`, because `s2[0]` is `"d"`.

So:

```python
dp[1][0] = True
```

The next character of `s3` is also `"a"`.

It can come from `s1[1]`.

So:

```python
dp[2][0] = True
```

The next character is `"d"`.

It comes from `s2[0]`.

So:

```python
dp[2][1] = True
```

The DP continues this way, always checking whether the next character can be explained by taking from `s1` or from `s2`.

At the end:

```python
dp[5][5] = True
```

So the answer is:

```python
True
```

## Correctness

The DP state `dp[i][j]` represents whether the first `i + j` characters of `s3` can be formed from the first `i` characters of `s1` and the first `j` characters of `s2`.

The base case `dp[0][0] = True` is correct because two empty prefixes form an empty prefix.

For any non-empty state, the last character of `s3[:i + j]` must come from either the last used character of `s1[:i]` or the last used character of `s2[:j]`.

If it comes from `s1`, then `s1[i - 1]` must equal `s3[i + j - 1]`, and the previous characters must form a valid interleaving represented by `dp[i - 1][j]`.

If it comes from `s2`, then `s2[j - 1]` must equal `s3[i + j - 1]`, and the previous characters must form a valid interleaving represented by `dp[i][j - 1]`.

The transition checks exactly these two cases.

Therefore, by induction over `i + j`, every DP entry is correct. The final entry `dp[m][n]` answers whether all of `s1` and all of `s2` form all of `s3`.

## Complexity

Let:

```python
m = len(s1)
n = len(s2)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(m * n)` | There are `(m + 1) * (n + 1)` states |
| Space | `O(m * n)` | The DP table stores all states |

## Implementation

```python
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m = len(s1)
        n = len(s2)

        if m + n != len(s3):
            return False

        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True

        for i in range(m + 1):
            for j in range(n + 1):
                if i > 0 and s1[i - 1] == s3[i + j - 1]:
                    dp[i][j] = dp[i][j] or dp[i - 1][j]

                if j > 0 and s2[j - 1] == s3[i + j - 1]:
                    dp[i][j] = dp[i][j] or dp[i][j - 1]

        return dp[m][n]
```

## Code Explanation

First store the string lengths:

```python
m = len(s1)
n = len(s2)
```

If the total length differs, return immediately:

```python
if m + n != len(s3):
    return False
```

Create the DP table:

```python
dp = [[False] * (n + 1) for _ in range(m + 1)]
```

The empty prefixes match:

```python
dp[0][0] = True
```

Then fill every state:

```python
for i in range(m + 1):
    for j in range(n + 1):
```

If the last character came from `s1`:

```python
if i > 0 and s1[i - 1] == s3[i + j - 1]:
    dp[i][j] = dp[i][j] or dp[i - 1][j]
```

If the last character came from `s2`:

```python
if j > 0 and s2[j - 1] == s3[i + j - 1]:
    dp[i][j] = dp[i][j] or dp[i][j - 1]
```

Finally:

```python
return dp[m][n]
```

## Space-Optimized Implementation

Since each row only depends on the previous row and the current row, we can use a one-dimensional DP array.

```python
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m = len(s1)
        n = len(s2)

        if m + n != len(s3):
            return False

        dp = [False] * (n + 1)
        dp[0] = True

        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0 and j == 0:
                    continue

                from_s1 = (
                    i > 0
                    and dp[j]
                    and s1[i - 1] == s3[i + j - 1]
                )

                from_s2 = (
                    j > 0
                    and dp[j - 1]
                    and s2[j - 1] == s3[i + j - 1]
                )

                dp[j] = from_s1 or from_s2

        return dp[n]
```

Space complexity becomes:

| Metric | Value |
|---|---|
| Time | `O(m * n)` |
| Space | `O(n)` |

## Testing

```python
def run_tests():
    s = Solution()

    assert s.isInterleave("aabcc", "dbbca", "aadbbcbcac") is True
    assert s.isInterleave("aabcc", "dbbca", "aadbbbaccc") is False
    assert s.isInterleave("", "", "") is True

    assert s.isInterleave("", "abc", "abc") is True
    assert s.isInterleave("abc", "", "abc") is True
    assert s.isInterleave("abc", "def", "adbcef") is True
    assert s.isInterleave("abc", "def", "abdecf") is True
    assert s.isInterleave("abc", "def", "abdfec") is False
    assert s.isInterleave("aa", "ab", "aaba") is True
    assert s.isInterleave("aa", "ab", "abaa") is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"aabcc", "dbbca", "aadbbcbcac"` | Main true example |
| `"aabcc", "dbbca", "aadbbbaccc"` | Main false example |
| Three empty strings | Empty base case |
| Empty `s1` | Must match only `s2` |
| Empty `s2` | Must match only `s1` |
| Mixed valid interleavings | Checks order preservation |
| Invalid order | Rejects broken source order |
| Repeated characters | Checks ambiguous choices |