# Check if given string is interleaving of two other given strings

Given three strings, return true if third string is interleaving of first and second string. i.e., it is formed from all characters of first and second string and order of characters is preserved.

For example,

ACDB is interleaving of AB and CD

ADEBCF is interleaving of ABC and DEF

ACBCD is interleaving of ABC and CD

ACDABC is interleaving of ABC and ACD

We can easily solve this problem using Recursion.

## C++

Output:

Given string is interleaving of X and Y

## Java

Output:

Given String is interleaving of X and Y

The time complexity of above solution is O(m + n) where m and n are the lengths of X and Y. Auxiliary space used by the program is O(1).

The problem with the above solution is that it doesn’t handle duplicates. Suppose X = “ABC” and Y = “ACD”, then above solution will return false for string S = “ACDABC”. The reason is that if the current character of S matches with current character of both X and Y, the solution will always pair S with X and do not check if solution can be formed by pairing S with Y or not.

We can easily handle duplicates by pairing S with both X and Y and recursively check if the solution can be formed by either of them or not. Below is C++ and Java implementation of the idea:

## C++

Output:

Given string is interleaving of X and Y

## Java

Output:

The worst case time complexity of above solution is exponential and worst case happens when all characters of X and Y are same. We can use Dynamic Programming to reduce worst case time complexity to O(mn) (DP will take O(mn) extra space).

The DP solution is discussed below in C++ and Java:

## C++

Output:

Given string is interleaving of X and Y

## Java

Output:

Given String is interleaving of X and Y