Find all interleavings of given strings

Find all interleavings of given strings that can be formed from all the characters of first and second string where order of characters is preserved.

For example, interleavings of string ABC and ACB are

ACBABC
AABCBC
ACABCB
ABCACB
AACBBC
ABACCB
ACABBC
ABACBC
AACBCB
AABCCB

We can easily solve this problem using recursion. The idea is to append first or last character of X and Y in the result one by one and recurse for remaining substring.

Input: X[1..m], Y[1..n]

fun(X, m, Y, n) = fun(X, m-1, Y, n) + X[m]
fun(X, m, Y, n-1) + Y[n]

fun(X, 0, Y, n) = Y[n]    // X is empty
fun(X, m, Y, 0) = X[m]    // Y is empty

Below is C++ and Java implementation of the idea:

Java

Output:

ACBABC
AABCBC
ACABCB
ABCACB
AACBBC
ABACCB
ACABBC
ABACBC
AACBCB
AABCCB

(3 votes, average: 3.67 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest
MessiCR7

If the question asks us to ensure there are no repetitions, what’s a good way of doing that?

Guest

This solution is wrong. See this http://javabypatel.blogspot.com/2016/03/print-all-interleaving-of-given-two-strings.html.

It should give 20 different strings for ABC and ACB. But yours is giving only 10.
Output is ABCACB
ABACCB
ABACCB
ABACBC
AABCCB
AABCCB
AABCBC
AACBCB
AACBBC
AACBBC
AABCCB
AABCCB
AABCBC
AACBCB
AACBBC
AACBBC
ACABCB
ACABBC
ACABBC
ACBABC