## Interleaving String Difficulty: Hard

#### 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

1. Brute Force
2. 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 :-

1. 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.
2. 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

1. 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`.
2. 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?)
3. Now if those are not the case, then move ahead with the two possibilities discussed above.
• If `S3 == S1`, then check for `S1[1…], S2, S3[1...]`
• If `S3 == S2` 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 == S1) and isInterleaved( S1 + 1, S2, S3 + 1))
or ((S3 == S2) 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(mn)

Space complexity: O(mn).

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!