# Interleaving Strings (C, Java, and Python Code)

Given three strings S1, S2 and S3. The task is to check whether the string S3 can be formed by an interleaving of strings S1 and S2.
S3
is said to be interleaving S1 and S2 if it contains all the characters of S1 and S2 and the order is preserved.

Examples:

Input:
s1 = “aabcc”
s2 = “dbbca”
Output: True
Explanation:

Input:
s1 = “aabcc”
s2 = “dbbca”

Output: False

## Approach 1: Brute Force

The most basic approach to solve this problem is to simply consider all possible strings of S1 and S2. If you observe carefully, there are two ways that needs to be taken care of:

• If S3[0] == S1[0], move to the next characters and recursively iterate the rest of the string of S1.
• If S3[0] == S2[0],  move to the next characters and recursively iterate the rest of the string of S2.

Algorithm:

• The base case of the recursive function is when the strings S1, S2 and S3 are empty.
• For the rest of the function, check whether S3[0] == S1[0], then recursively traverse for S1[1…N]
• Similarly, if S3[0] == S2[0], then recursively traverse for S2[1…N].

Implementation of the Approach:

### C++ Code

```bool isInterleaving(string X, string Y, string S) {
if (!X.length() &amp;&amp; !Y.length() &amp;&amp; !S.length()) {
return true;
}

if (!S.length()) {
return false;
}

if (X.length() &amp;&amp; S[0] == X[0]) {
return isInterleaving(X.substr(1), Y, S.substr(1));
}

if (Y.length() &amp;&amp; S[0] == Y[0]) {
return isInterleaving(X, Y.substr(1), S.substr(1));
}

return false;
}```

### Java Code

```public static boolean isInterleaving(String X, String Y, String S) {
if (X.length() == 0 &amp;&amp; Y.length() == 0 &amp;&amp; S.length() == 0) {
return true;
}

if (S.length() == 0) {
return false;
}

if (X.length() != 0 &amp;&amp; S.charAt(0) == X.charAt(0)) {
return isInterleaving(X.substring(1), Y, S.substring(1));
}

if (Y.length() != 0 &amp;&amp; S.charAt(0) == Y.charAt(0)) {
return isInterleaving(X, Y.substring(1), S.substring(1));
}

return false;
}```

### Python Code

```def isInterleaving(X, Y, S):
if not X and not Y and not S:
return True

if not S:
return False

if X and S[0] == X[0]:
return isInterleaving(X[1:], Y, S[1:])

if Y and S[0] == Y[0]:
return isInterleaving(X, Y[1:], S[1:])

return False```

Time Complexity: O(2^(N+M)), where N and M is the length of the string S1 and S2.

Space Complexity: O(N + M), for the recursive stack.

## Approach 2: Dynamic Programming

In the previous approach, if you observe carefully, there were many overlapping subproblems which we were calculating again and again.

For example :

To avoid repetitive calculations, the idea is to use Dynamic Programming to solve the problem. The DP table is built as follows. Consider the following example:

Algorithm:

• Create a 2D dp array of size N X M, where N is the size of S1 and M is the size of S2.
• Run a nested loop from i = 0 till i = N+1 and j = 0 till j =  M + 1 and fill the table as follows:
• If i == 0 and j == 0:
• Dp[i][j] = True
• Else if i == 0 and S2[j – 1] == S3[i + j – 1]:
• Dp[i][j] = dp[i][j – 1] + 1
• Else if j == 0 and S1[j – 1] == S3[i + j – 1]:
• Dp[i][j] = dp[i – 1][j] + 1
• Else:
• (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[N][M]

Implementation of the Approach:

### C++ Code

```bool isInterleaving(string X, string Y, string S) {
int M = X.size();
int N = Y.size();

if (M + N != S.size()) {
return false;
}

bool T[M + 1][N + 1];

for (int i = 0; i &lt;= M; i++) {
for (int j = 0; j &lt;= N; j++) {
if (i == 0 &amp;&amp; j == 0) {
T[i][j] = true;
} else if (i and j and X[i - 1] == S[i + j - 1] and Y[j - 1] == S[i + j - 1]) {
T[i][j] = T[i - 1][j] || T[i][j - 1];
} else if (i and X[i - 1] == S[i + j - 1]) {
T[i][j] = T[i - 1][j];
} else if (j and Y[j - 1] == S[i + j - 1]) {
T[i][j] = T[i][j - 1];
}
}
}
return T[M][N];
}```

### Java Code

``` public static boolean isInterleaving(String X, String Y, String S) {
int M = X.length();
int N = Y.length();
if (M + N != S.length()) {
return false;
}
boolean[][] T = new boolean[M + 1][N + 1];
for (int i = 0; i &lt;= M; i++) {
for (int j = 0; j &lt;= N; j++) {
if (i == 0 &amp;&amp; j == 0) {
T[i][j] = true;
} else if (i != 0 &amp;&amp; j != 0 &amp;&amp; X.charAt(i - 1) == S.charAt(i + j - 1) &amp;&amp;
Y.charAt(j - 1) == S.charAt(i + j - 1)) {
T[i][j] = T[i - 1][j] || T[i][j - 1];
} else if (i != 0 &amp;&amp; X.charAt(i - 1) == S.charAt(i + j - 1)) {
T[i][j] = T[i - 1][j];
} else if (j != 0 &amp;&amp; Y.charAt(j - 1) == S.charAt(i + j - 1)) {
T[i][j] = T[i][j - 1];
}
}
}
return T[M][N];
}```

### Python Code

```def isInterleaving(X, Y, S):
M, N = len(X), len(Y)
if M + N != len(S):
return False

T = [[False for x in range(N + 1)] for y in range(M + 1)]

for i in range(0, M + 1):
for j in range(0, N + 1):

if i == 0 and j == 0:
T[i][j] = True

elif i and j and X[i - 1] == S[i + j - 1] and Y[j - 1] == S[i + j - 1]:
T[i][j] = T[i - 1][j] or T[i][j - 1]

elif i and X[i - 1] == S[i + j - 1]:
T[i][j] = T[i - 1][j]

elif j and Y[j - 1] == S[i + j - 1]:
T[i][j] = T[i][j - 1]

return T[M][N]```

Time Complexity: O(N*M), where N and M is the length of the string S1 and S2.

Space Complexity: O(N * M), since dp array is used.

Practice Questions:

Interleaving Strings

## FAQ

• What are the two types of possibilities for interleaving?
The two types of possibilities are as follows:
1. If S3[0] == S1[0], move to the next characters and recursively iterate the rest of the string of S1.

If S3[0] == S2[0],  move to the next characters and recursively iterate the rest of the string of S2.