Interview Question: Print all interleavings of two strings

Given two strings, write code to print all interleavings of these strings. For example: if the two strings are
"AB" & "12", then the output should be:

AB12
A1B2
A12B
1AB2
1A2B
12AB

Note that the order of characters in the individual strings are not changed in the output.

The logic for this is simple, we will use one character from each string and put it in the result. This function requires recursion. The main function to print interleavings will just allocate memory for the result string (If there are m & n characters in the 2 strings, then number of characters in the resultant string will be m+n)

void printInterleaving(char* a, char* b)
{
    // allocate memory to result string
    char * res = new char[strlen(a) + strlen(b) + 1];

    // Call the recursive function to print interleavings
    printInter(a, b, res, 0);

    // Delete memory allocated to result string
    delete[] res;
}

The recursive function is where the actual code will be.

void printInter(char* a, char* b, char* res, int i=0)
{
    // If both the strings are empty then print the result.
    if(*a == '\0' && *b == '\0')
    {
        res[i] = '\0';
        cout<<"\n"<<res;
    }

    // Add first character of string a to result
    if(*a != '\0')
    {
        res[i] = *a;
        printInter(a+1, b, res, i+1);
    }
   
    // Add first character of string b to result
    if(*b != '\0')
    {
        res[i] = *b;
        printInter(a, b+1, res, i+1);
    } 
}

Time Complexity: O(m!.n!).  This is the total number of interleavings for the 2 strings.

Interview Questions Archive:

         To see all the questions in the category Click Here...