Interleaving Strings

Problem Statement

This is a question from one of the interview experiences. The statement, “Given three strings A, B and C find if C is an interleaving of A and B.” Interleaving is defined as below:
A string C is said to be an interleaving of two strings A and B if C contains a sub sequence of A and B such that the relative order of characters in A and in B are preserved in C.

For e.g. :

  • A – ABCD
  • B – BACDX
  • C – ABACDXBCD

The Idea – Interleaving Strings

Here I am not giving any solution which is less than O(M*N) solution where M is the length of the shortest string among A and B and N is the length of the string C. We will analyze that later. I do not promise this to be the most efficient algorithm but yes it passes for all test cases because the approach is simple.

Let us solve the problem in steps.

Step 1

The idea is to find all possible sub sequences of A in C. We are interested in all list of indices in C which represents the sub sequence of characters of A in C.
For the above case, I see two sub sequences in C for the characters in A. The indices for these would be (0, 1, 3, 4) and (0, 6, 7, 8).

To find these indices we can follow the below approach.

  • Create a table with column values from characters of String C and row values from characters of String A
  • Traverse through each row and if the row and column values match, mark that cell as 1. Rest all is anyways zero.
  • Refer the below table for reference.

Interleaving Strings

If you notice, only the cells where the row and column values matches contains the value 1.
For memory optimization you can avoid this table, because the data is too sparse. If you want, use a list of integer arrays of variable length.

Step 2

From this table let us create a tree of indices. Each path of this tree will give us the indices of one sub sequence. How to create the tree?

  • The tree must contain just one root, so assign a dummy root with value -1.
  • Iterate through each row of the table and if there is a 1 in any cell, then we can create a node out of that cell and add it to the tree.
  • For each node in the tree at a given level, add children to the node from the next level (next row in the table). You can only add children if the parent node has a value lower than the child.
  • Refer the below tree for the above table.

Interleaving Strings

If you notice the second level in the tree, it contains two nodes (0 and 2), because the first row has only these two cell values as 1.
The node 0 in the tree, has children (1 and 6) because the second row has cells 1 and 6 as value 1.
The node 2 in the tree, has child (6) because the second row has cells 1 and 6 as value 1 but only 6 is bigger than 2.
The node 1 in the tree, has children (3 and 7) because the third row has cells 3 and 7 as value 1.
The node 6 in the tree, has child (7) because the third row has cells 3 and 7 as value 1 but only 7 is bigger than 6.

I think you got the idea. We populate the whole tree like this and end up with the above tree.

Step 3

Now find all possible paths in the tree and store it in a list off integer arrays.
So the paths would be as below:

  • -1, 0, 1, 3, 4
  • -1, 0, 1, 3, 8
  • -1, 0, 1, 7, 8
  • -1, 0, 6, 7, 8
  • -1, 2, 6, 7, 8

So these are the five sub sequence indices.

Step 4

Now iterate through each path one by one and remove those characters from a copy of the string C. Compare the remaining characters in C with the string B. If they match, then C is interleaving of A and B.

For e.g.:
Processing path 1 : Remove characters at 0, 1, 3 and 4 from the string C (ABACDXBCD), it gives us (AXBCD). Check if this matches string B (BACDX). It doesn’t, so we move to the next path.
Processing path 2 : Remove characters at 0, 1, 3 and 8 from the string C (ABACDXBCD), it gives us (ADXBC). Check if this matches string B (BACDX). It doesn’t, so we move to the next path.
Processing path 3 : Remove characters at 0, 1, 7 and 8 from the string C (ABACDXBCD), it gives us (ACDXB). Check if this matches string B (BACDX). It doesn’t, so we move to the next path.
Processing path 4 : Remove characters at 0, 6, 7 and 8 from the string C (ABACDXBCD), it gives us (BACDX). Check if this matches string B (BACDX). It does match, so we break out of the loop and return true.

In case all the paths were processed and there were no matches, then we would have returned false.

Below is the source code for the same. This might look too much of code because, we wrote the code for finding all paths, creating the tree etc. For complete source code, please visit Github for Techieme.

Source Code – Interleaving Strings

Analysis

Before doing some analysis, I would just suggest you to optimize this code for boundary conditions and quit even before running through the step 1. For e.g. you can do a length check and other basic checks to quit early. Although the code will catch it, but you can still break early.

Time Complexity :

Table Creation : O(M * N)
Tree Creation : O(M * N) : Actually it is too less than this but the worst case is O(M * N)
Finding Path : O(M * N) – as we are looking for each node in the tree, and the max number of nodes would be M * N. (In average scenario much less).
Searching the string in Step 4 takes time equal to the number of paths, which is equal to the number of leaves in the tree, which can be at most O(N)

Hence the running time would b of the order O(M * N)

Space Complexity

The table takes a max of O(M * N)
The tree will cost us a max of O(M * N)
The paths will cost same as O (M * N)
So, the space required would be maximum off the order O(M * N)

Remember, this is not really optimized code. You have a lot of scope to optimize it.

Don’t forget to subscribe to TechieMe to get updates on latest posts.

  • Sridhar Jayapaul

    Why so much Complication ? Does interviewer expects the same becoz this can be done easily with Regex as below

    static boolean isInterLeaving(String A, String B, String C) {
    // Checks whether B is part of C
    // If So replace with empty such the the new string should be equal to A
    if (C.replaceAll(B, “”).equals(A) )
    return true;
    return false;
    }

  • madno

    With dp: