Interleaving Two Strings
You are given three strings 'A', 'B' and 'C'. Check whether 'C' is formed by an interleaving of 'A' and 'B'.

'C' is said to be interleaving 'A' and 'B', if the length of 'C' is equal to the sum of the length of 'A' and length of 'B', all the characters of 'A' and 'B' are present in 'C' and the order of all these characters remains the same in all three strings.

For Example:

If A = “aab”, 'B' = “abc”, 'C' = “aaabbc” Here 'C' is an interleaving string of 'A' and 'B'. because 'C' contains all the characters of 'A' and 'B' and the order of all these characters is also the same in all three strings.

If 'A' = “abc”, 'B' = “def”, 'C' = “abcdefg” Here 'C' is not an interleaving string of 'A' and 'B'. 'B'ecause neither A nor 'B' contains the character ‘g’.

Input format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow. The first and only line of each test case contains three strings 'A', 'B' and 'C' each separated by a single space.

Output format:

For each test, print True, if 'C' is an interleaving string of 'A' and 'B, otherwise print False in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

'C'onstraints:

1

Question

Interleaving Two Strings

You are given three strings 'A', 'B' and 'C'. Check whether 'C' is formed by an interleaving of 'A' and 'B'.

'C' is said to be interleaving 'A' and 'B', if the length of 'C' is equal to the sum of the length of 'A' and length of 'B', all the characters of 'A' and 'B' are present in 'C' and the order of all these characters remains the same in all three strings.

For Example:

If A = “aab”, 'B' = “abc”, 'C' = “aaabbc”
Here 'C' is an interleaving string of 'A' and 'B'. because 'C' contains all the characters of 'A' and 'B' and the order of all these characters is also the same in all three strings.

interleaving

If 'A' = “abc”, 'B' = “def”, 'C' = “abcdefg”
Here 'C' is not an interleaving string of 'A' and 'B'. 'B'ecause neither A nor 'B' contains the character ‘g’.

Input format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first and only line of each test case contains three strings 'A', 'B' and 'C' each separated by a single space.

Output format:

For each test, print True, if 'C' is an interleaving string of 'A' and 'B, otherwise print False in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

'C'onstraints:

1 <= T <= 10
1 <= |'A'|, |'B'| <= 150
1 <= |'C'| <= 300

where |A|, |'B'|, |'C'| denotes the length of string 'A', 'B' and 'C' respectively.   
All the characters of the strings 'A', 'B' and 'C' contain lowercase English letters only.

Time limit: 1 sec

Accepted Answer

Solution Steps:

1 . Create a DP array (matrix) of size M*N, where m is the size of the first string, and n is the size of the second string. 2. Initialize the matrix to false.
3. If the sum of sizes of smaller strings is not equal to the length of the larger string, then return false and break the
array as they cant be interleaved to form the larger string.
4. Run a nested loop, the outer loop from 0 to m and the inner loop from 0 to n. Loop counters are i and j.
5. If the values of i and j are both zeroes then mark dp[i][j] as true. If the value of i is zero and j is non zero and the j-1
character of B is equal to j-1 character of C the assign dp[i][j] as dp[i][j-1] and similarly if j is 0 then match i-1 the
character of C and A and if it matches then assign dp[i][j] as dp[i-1][j].
6. Take three characters x, y, z as (i-1)th character of A and (j-1)th character of B and (i + j – 1)th character of C.
7. if x matches with z and y does not match with z then assign dp[i][j] as dp[i-1][j] similarly if x is not equal to z and y is
equal to z then assign dp[i][j] as dp[i][j-1]
8. if x is equal to y and y is equal to z then assign dp[i][j] as bitwise OR of dp[i][j-1] and dp[i-1][j].
9. return value of dp[m][n].

Accepted Answer

Brute-force

Approach:

In order to solve this problem, let us solve a smaller problem first. Let’s assume that the length of the string A and B is 1 and the length of the string C is 2. Now in order to check whether C is formed by interleaving A and B or not, we consider the last character of string C and if this character matches neither with the character of the string A nor with the character of string B, then we return false. But if it matches with any of the characters either from A or from B, we check the same for the other character in C. So, let's further expand this idea, for bigger problems. So, if the last character of C, matches with either the last character of A or B, we check recursively for the second last element and then the third last element and so on, until we finally reach the base case when all the strings eventually become empty.

Steps:

We create a recursive function let’s say isInterleaveUtil and pass A, B, C, n1, n2, n3 as arguments, where n1,n2, and n3 are the length of A, B, and C.

bool isInterleaveUtil( A, B, C, n1, n2, n3):

If all the strings become empty i.e n1,n2.and n3 become 0, then simply return true.
If the length of C is not equal to (length of A + length of B),i.e n1+n2 != n3 then we simply return false.
If the last character of both A and B matches with the last character of C, then we check for both the cases i.e. retreating A by one character and B by one character i.e call isInterleaveUtil(A, B, C, n1-1, n2, n3-1) and isInterleaveUtil(A, B, C, n1, n2-1, n3-1), and return true, if either of them returns true.
If the last character of C matches with the last character of A, but not with the last character of B, we move one character back in A and check recursively. I.e. call isInterleaveUtil(A, B, C, n1-1, n2, n3-1);
If the last character of C matches with the last character of B, but not with the last character of A, we move one character back in B and check recursively. I.e. call isInterleaveUtil(A, B, C, n1, n2-1, n3-1).
If the last character of C matches neither with the last character of A nor with the last character of B, then we simply return false.

Space Complexity: O(n)Explanation:

O(N + M), where N is the length of the string A and M is the length of string B.

In the worst case, the size of stack for recursive calls can go upto (N + M). Hence the overall complexity will be O(N + M).

Time Complexity: O(2^n)Explanation:

O(2^(N + M)), where N is the length of the string A and M is the length of string B.

In the worst case, for every character of the input strings A and B, there can be two choices. Hence, the time complexity will be O(2^(N + M)).

Accepted Answer

Dynamic Programming with memoization

In the previous approach, the algorithm recursively calculates and compares every possible character of A and B with C, which has many overlapping subproblems. i.e. recursive function computes the same sub-problems again and again. So we can use memoization to overcome the overlapping subproblems. To reiterate, memoization is when we store the results of all previously solved subproblems and return whether C is formed by interleaving A and B or not, from the dp[i][j] if we encounter the problem that has already been solved.

Since there are three states those are changing in the recursive function, but the change in the string C is just a result of a change in string A and string B, so we use the 2-dimensional array dp[][] to store all the subproblems where dp[i][j] will store whether C is formed by interleaving A from 0 to ith character and B from 0 to jth character or not.

Steps:

Create a dp array of size (N+1 * M+1) where N and M are lengths of A and B respectively. Initialize dp table to -1 initially.
Then we create a recursive function let’s say isInterleavingUtil and pass A, B, C, n1, n2, n3 and the dp array as arguments, where n1,n2, and n3 are the length of A, B, and C.

bool isInterleaveUtil( A, B, C, n1, n2, n3, dp):

If all the strings become empty i.e n1,n2.and n3 become 0, then simply return true.
If the length of C is not equal to (length of A + length of B),i.e n1+n2 != n3 then we simply return false.
If we already solve the same subproblem for the remaining of strings A, B and C i.e. dp[n1][n2] != -1, then return dp[n1][n2].
If the last character of both A and B matches with the last character of C, then we check for both the cases i.e. retreating A by one character and B by one character i.e call isInterleaveUtil(A, B, C, n1-1, n2, n3-1, dp) and isInterleaveUtil(A, B, C, n1, n2-1, n3-1, dp), and store the result of both functions in dp[n1][n2], and return true, if either of them returns true.
If the last character of C matches with the last character of A, but not with the last character of B, we move one character back in A and check recursively. I.e. call isInterleaveUtil(A, B, C, n1-1, n2, n3-1, dp), then store the result of function in dp[n1][n2]
If the last character of C matches with the last character of B, but not with the last character of A, we move one character back in B and check recursively. I.e. call isInterleaveUtil(A, B, C, n1, n2-1, n3-1, dp), then store the result of function in dp[n1][n2].
If the last character of C matches neither with the last character of A nor with the last character of B, then we simply return false.

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N*M), where N is the length of the string A and M is the length of string B.

In the worst case, extra space is required to create the dp array of size N*M i.e O(N*M) and also for the recursion stack. Hence, the overall complexity will be O(N*M).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N*M), where N is the length of the string A and M is the length of string B.

In the worst case, for every pair of characters in A and B, it is being computed only once. So the overall time complexity will be O(N*M).

Accepted Answer

Bottom-Up DP

Approach:

The idea is to use a bottom-up dynamic programming approach instead of a memoization approach. In this, we use the recurrence relation of memoization approach as dp[i][j] = (dp[i-1][j] && A[i-1] == C[i+j-1]) || (dp[i][j-1] && B[j-1] == C[i+j-1]); where i is in [0, N] and j is in [0, M], where N and M is the length of string A and string B respectively.

Steps:

Create a dp array of size (N+1 * M+1) where N and M are lengths of A and B respectively. Initialize dp array to false initially.
If the length of C is not equal to (length of A + length of B), then we simply return false.
Run a loop from 0 to N and inside that run another loop from 0 to M, let’s denote the loop counters as i and j respectively.
Mark dp[i][j] as true, if the values of i and j are both zeroes. If the value of i is zero and j is non zero, then dp[i][j] becomes true, if dp[i][j-1] is true and the (j-1)th character of B matches with (j-1)th character of C. Similarly if j is 0, then dp[i][j] becomes true, if dp[i-1][j] is true and the (i-1)th character of A matches with (i-1)th character of C.
Now check for (i-1)th character of A, (j-1)th character of B and (i+j-1)th character of C.
If (i-1)th character of A matches with (i+j-1)th character of C and (j-1)th character of B doesn’t match with (i+j-1)th character of C, then mark dp[i][j] as dp[i-1][j].
If (i-1)th character of A doesn’t match with (i+j-1)th character of C and (j-1)th character of B matches with (i+j-1)th character of C, then mark dp[i][j] as dp[i][j-1].
If both (i-1)th character of A and (j-1)th character of B match with (i+j-1)th character of C, then mark dp[i][j] as true if either of dp[i-1][j], dp[i][j-1] is true, else mark dp[i][j] as false.
Finally, return dp[N][M].

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N*M), where N is the length of the string A and M is the length of string B.

In the worst case, extra space is required to create the dp array of size N*M. Hence the overall complexity will be O(N*M).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N*M), where N is the length of the string A and M is the length of string B.

In the worst case, traversing the dp array of size N*M i.e O(N*M). Hence the overall complexity will be O(N*M).

Accepted Answer

1D Dynamic Programming

Approach:

The space complexity for the last two approaches is O(N*M), however, it can be improved further to O(min(M,N)), if we use 1D dp array. The approach is the same as the previous approach except for the fact that here we use 1D dp array to store the results of the prefixes of the strings processed so far. We update dp[i] by using the value of dp[i-1] and the previous value of dp[i].

Steps:

If N is less than M, create a dp array of size equal N + 1, else create a dp array of size M + 1, where N is the length of A and M is the length of B. We do so in order to improve the space complexity further.
If the length of C is not equal to (length of A + length of B), then we simply return false.
Run a loop from 0 to N and inside that run another loop from 0 to M, let’s denote the loop counters as i and j respectively.
Mark dp[j] as true, if the values of i and j are both zeroes.
If the value of i is zero and j is non zero and the (j-1)th character of B matches with (j-1)th character of C, then assign dp[j] as dp[j-1].
If the value of j is zero and i is non zero and the (i-1)th character of A matches with (i-1)th character of C, then dp[j] remains unchanged.
If dp[j] is true and if (i-1)th character of A matches with (i+j-1)th character of C then it remains true. Else if dp[j] is false or dp[j-1] is true and (j-1)th character of B matches with (i+j-1)th character of C, then dp[j] is true. Else if both dp[j] and dp[j-1] are false, then dp[j] is false.
Finally, return the dp[M].

Space Complexity: O(n)Explanation:

O(min(M, N)), where N is the length of the string A and M is the length of string B.

In the worst case, we are creating a DP array of size O(min(M, N)). Hence, the space complexity becomes O(min(M, N)).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N*M), where N is the length of the string A and M is the length of string B.

In the worst case, Traversing the DP array of size N*M i.e O(N*M). Hence the overall complexity will be O(N*M).

You are given three strings 'A', 'B' and 'C'. Check whether 'C' is formed by an interleaving of 'A' and 'B'.

'C' is said to be interleaving 'A' and 'B', if the length of 'C' is equal to the sum of the length of 'A' and length of 'B', all the characters of 'A' and 'B' are present in 'C' and the order of all these characters remains the same in all three strings.

For Example:

Input format:

Output format:

Note:

'C'onstraints:

Steps:

Approach:

Top Cisco Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Cisco Software Engineer