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 interleavingS1
andS2
if it contains all characters ofS1
andS2
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 ofS1
, we move to the next character ahead inS1
andS3
and recursively call the function. 
If the first character of
S3
matches the first character ofS2
, we move to the next character ahead inS2
andS3
and recursively call the function.
Solution Step

Check if
S1
,S2,
andS3
are empty, then return True. This will be the base case for our recursive function as emptyS3
is interleaving ofS1
andS2
. 
Check if
S3
is empty and either ofS1
andS2
is not empty, then return False, which will meanlen(S3)
is smaller thanlen(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 forS1[1…], S2, S3[1...]

If
S3[0] == S2[0]
then check forS1, 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 ofS1
and the first character ofS2
?
2. Dynamic Programming
The above recursive solution certainly has many overlapping subproblems. 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 twodimensional
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
i1, j
, and if
i1,j
is already interleaving and
i
and current
S3
position are equal, then they are interleaving. If we arrive
i,j
from
i, j1
, and if
i, j1
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
. Wherem
andn
are the lengths ofS1
andS2
 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][j1] and S2[j1] == S3[i+j1])
else if(j == 0)
DP[i][j] = ( DP[i1][j] and S1[i1] == S3[i+j1])
else
DP[i][j] = (DP[i1][j] and S1[i1] == S3[i+j1] ) or
(DP[i][j1] and S2[j1] == S3[i+j1] )
}
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[i1][j] & s3[i+j1] == s1[i1])  (dp[i][j1] & s2[j1] == s3[i+j1])
?  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!