## Interleaving String

**Difficulty: **Hard

**Asked in: **Google, Microsoft, Yahoo

#### Understanding The Problem

**Problem Description**

Given three strings `S1`

**, **`S2`

and `S3`

, write a program that checks whether `S3`

is an interleaving of `S1`

and `S2`

**.**

**Problem Note:**

`S3`

is said to be interleaving`S1`

and`S2`

if it contains all characters of`S1`

and`S2`

and the order of all characters in individual strings is preserved.

**Example 1**

```
Input: S1 = "xxyzz", S2 = "wyyzx" and S3 = "xxwyyzyzxz"
Output: true
Explanation:"xx" (from S1) + "wyyz" (from S2) + "yz" (from S1) + "x" (from S2) + "z" (from S1)
```

**Example 2**

```
Input: S1 = "xxyzz", S2 = "wyyzx", S3 = "xxwyyyxzzz"
Output: false
Explanation: It is not possible to get S3 by interleaving S1 and S2.
```

#### Solutions

**Brute Force****Dynamic Programming**

You may try this problem here.

#### 1. Brute Force Approach

If you will look at the above examples, you will conclude that there are two possibilities that need to be taken care of :-

- If the first character of
`S3`

matches the first character of`S1`

, we move to the next character ahead in`S1`

and`S3`

and recursively call the function. - If the first character of
`S3`

matches the first character of`S2`

, we move to the next character ahead in`S2`

and`S3`

and recursively call the function.

**Solution Step**

- Check if
`S1`

,`S2,`

and`S3`

are empty, then return True. This will be the base case for our recursive function as empty`S3`

is interleaving of`S1`

and`S2`

. - Check if
`S3`

is empty and either of`S1`

and`S2`

is not empty, then return False, which will mean`len(S3)`

is smaller than`len(S1) + len(S2)`

**(How?)** - Now if those are not the case, then move ahead with the two possibilities discussed above.

- If
`S3[0] == S1[0]`

, then check for`S1[1…], S2, S3[1...]`

- If
`S3[0] == S2[0]`

then check for`S1, S2[1…], S3[1…]`

- If any of the above mentioned two possibilities is true, then return true, otherwise false

**Pseudo Code**

```
bool isInterleaved( char[] S1, char S2, char S3) {
// Base Case: If all strings are empty
if ( not (len(S1) != 0 or len(S2) != 0 or len(S3) != 0) )
return true
if (len(S3) == 0)
return false
return ((S3[0] == S1[0]) and isInterleaved( S1 + 1, S2, S3 + 1))
or ((S3[0] == S2[0]) and isInterleaved( S1, S2 + 1, S3 + 1))
}
```

**Complexity Analysis**

**Time Complexity: **O(2^n)

For every character of `S3`

, there can be 2 options so the time complexity is O(2^n).

**Space Complexity: **O(1), not considering recursion stack space.

**Critical Ideas To Think**

- Can you explain, how did the base help in solving the problem?
- What did we do, when the first character of
`S3`

matches with both the first character of`S1`

and the first character of`S2`

?

#### 2. Dynamic Programming

The above recursive solution certainly has many overlapping sub-problems. For example, if we consider S1 = “AAA”, S2 = “AAA” and S3 = “AAAAAA” and draw recursion tree, there will be many overlapping subproblems. Therefore, the solution to this problem could be optimized using Dynamic Programming.

The idea is to build a two-dimensional **DP** table, according to the drawn path displayed below. Because it’s interleaving, so certain order still needs to be maintained, so that’s why for a valid path, it can only go right or down. That’s why `DP[i][j]`

is depending on `DP[i - 1][j]`

and `DP[i][j - 1]`

.

After discovering the transition rule to get `DP[i][j]`

, we just need to record true or false in the **DP** table. `DP[i][j]`

means if `s3.substr(0, i + j)`

can be formed by `s1.substr(0, i)`

interleaving `s2.substr(0, j)`

.

If you will look over the above example, you will understand how will DP table will help to build the solution.

To implement this method, we’ll make use of a 2D boolean **DP** array. In this array `DP[i][j]`

implies if it is possible to obtain a substring of length (i+j+2) which is a prefix of `S3`

by some interleaving of prefixes of strings `S1`

and `S2`

having lengths (i+1) and (j+1) respectively.

In short, **DP** table represents if `S3`

is interleaving at (i+j)th index when `S1`

is at `ith`

index, and `S2`

is at `jth`

index. `0th`

index means an empty string.

So, if both `S1`

and `S2`

is currently empty, `S3`

is empty too, and it is considered interleaving. If only, `S1`

is empty, then if the previous `S2`

position is interleaving and the current `S2`

position character is equal to S3 current position character, it is considered interleaving. A similar idea applies when `S2`

is empty. when both `S1`

and `S2`

are not empty, then whenever we arrive `i, j`

from `i-1, j`

, and if `i-1,j`

is already interleaving and `i`

and current `S3`

position are equal, then they are interleaving. If we arrive `i,j`

from `i, j-1`

, and if `i, j-1`

is already interleaving and `j`

and current `S3`

position equal then also it is interleaving.

**Visualization for a example**

**Solution Steps**

- Create a 2D boolean DP array of size
`m+1, n+1`

. Where`m`

and`n`

are the lengths of`S1`

and`S2`

- Now fill the DP table by comparing the characters of S1, S2 with S3 accordingly.
- Return
`DP[m][n]`

**Pseudo Code**

```
bool isInterleave(char[] S1, char[] S2, char[] S3) {
if(S3.length() != S1.length() + S2.length())
return false
bool DP[S1.length()+1][S2.length()+1]
for(int i=0 to i < s1.length()+1)
for(int j=0 to j < s2.length()+1){
if(i==0 and j==0)
DP[i][j] = true
else if(i == 0)
DP[i][j] = ( DP[i][j-1] and S2[j-1] == S3[i+j-1])
else if(j == 0)
DP[i][j] = ( DP[i-1][j] and S1[i-1] == S3[i+j-1])
else
DP[i][j] = (DP[i-1][j] and S1[i-1] == S3[i+j-1] ) or
(DP[i][j-1] and S2[j-1] == S3[i+j-1] )
}
return DP[S1.length()][S2.length()]
}
```

**Complexity Analysis**

Time complexity: *O*(*m*⋅*n*)

Space complexity: *O*(*m*⋅*n*).

Where m and n are the lengths of S1 and S2 respectively.

**Critical Ideas To Think**

- Can you prove that the transaction formula for this problem is
`dp[i][j] = (dp[i-1][j] & s3[i+j-1] == s1[i-1]) || (dp[i][j-1] & s2[j-1] == s3[i+j-1])`

? - Can you think of a BFS approach for this problem?
- The two possibilities discussed in the recursion approach have been taken care of in this approach. How?
- An approach is to just merge the two strings. A pointer into each string. If the present character in the interleaved string c equals one of the strings a or b, increase the pointer to that string and to c, if not then return false. Do this for every character in c. Complexity will be O(m+n). Do you think, this approach will work? If not then, can you find a failing test case for such an approach?

#### Comparison Of Solutions

#### Suggested Problems To Solve

- Longest Palindromic Substring
- Longest Valid Parentheses
- Edit Distance
- Distinct Subsequences

If you have any more approaches or you find an error/bug in the above solutions, please comment down below.

**Happy Coding!**

**Enjoy Algorithms!**