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

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