Interleaving String

#Day 9

The interleaving string is a combination of two string such that order of characters in both the string is preserved in the interleaving string.


One of the interleaving string of “abc and abd is ababcd.

Checking for the interleaving string can be solved in O(nm)  using dynamic programming. Where n is the size of string 1 and m is the size of string 2.

For this, we create a table of size (n+1)*(m+1).

We fill the row 0 and column 0 first and then the rest of the table with the following rule.

  • [rowIndex + columnIndex-1] is the index in interleaving string.
  • rowIndex-1 is the index in string 2.
  • columnIndex -1 is the index in string 1.

We compare Interleaving string index value with string 2 index value and string 1 index value. Then we process it according to the following rule.

  • If interleaving string value == string 1 index value and left column of the field is 1.
    • Then  mark the field with 1
  • ELSE IF  interleaving string value == string 2 index value and  column just above the field is 1.
    • Then  mark the field with 1
  • ElSE:
    • Mark it as 0

On any given position 1 means. That by this point it is true of the interleaving string. And 0 means it is not.

def isInterleaving(stringA,stringB,interleavingString):
    lenStringA = len(stringA)
    lenStringB = len(stringB)
    interleavingTable =constructTable(stringA,stringB,interleavingString,lenStringA,lenStringB)
    for rowIndex in xrange(1,lenStringB+1):
        for columnIndex in xrange(1,lenStringA+1):
            if interleavingString[rowIndex+columnIndex-1]==stringA[columnIndex-1] and interleavingTable[rowIndex][columnIndex-1]==1:
            elif interleavingString[rowIndex+columnIndex-1]==stringB[rowIndex-1] and interleavingTable[rowIndex-1][columnIndex]==1:
                interleavingTable[rowIndex][columnIndex] = 0
    return interleavingTable[lenStringB][lenStringA]

Let’s see this with an example-

is1table[0][0] is initialized with 1 because the empty string can be the part of the interleaving string.


string 1[0]==interleavingString[0] and left field is 1

So we mark the current one as 1.




Then we fill the column 0 as



and the rest of the table is marked with the same rule. And we get the final table as


We Return the table[lastRow][lastColumn] which is 1. Hence the given string is the interleaving string of string 1 and string 2.

Time Complexity

The time complexity of this algorithm is O(nm). n and m are the lengths of string 1 and string 2 respectively.

Source Code

Source code for the implementation of this problem can be found here.


This article is inspired from the Tushar’s Youtube Channel.



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s