CareerCup

It is just like a restricted Permutation. Below is the Code.

public static void printInterleavings(String s1,String s2){
		printInterleavings(s1,s2,"");
	}
	
	
	public static void printInterleavings(String s1,String s2,String soFar){
		if((s1==null||s1.length()==0) && (s2==null||s2.length() == 0))
			return;
		if(s1==null || s1.length()==0){
			System.out.print(" " + soFar + s2 +" ");
			return;
		}
		if(s2==null || s2.length()==0){
			System.out.print(" " + soFar + s1 +" ");
			return;
		}
		printInterleavings(s1.substring(1), s2, soFar + s1.charAt(0));
		printInterleavings(s1, s2.substring(1), soFar + s2.charAt(0));
		
	}

Source: puddle of riddles

void interleave(char* str1, char* str2, char* str, int len)
{
    int i=0;

    if(str1[0] == '\0' && str2[0] == '\0')
    {
        printf("%s\n", str-len);
        return;
    }

    if(str1[0] != '\0')
    {
        str[0] = str1[0];
        interleave(str1+1, str2, str+1, len);
    }
    if(str2[0] != '\0')
    {
        str[0] = str2[0];
        interleave(str1, str2+1, str+1, len);
    }
}

int main()
{
    char* str1 = "AB";
    char* str2 = "MNO";
    
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int len = len1+len2;

    char* str = (char*)malloc(len+1);
    memset(str, 0, len+1);

    interleave(str1, str2, str, len);
    return 0;
}

#include <iostream>
using namespace std;

void interleavings(string pre, string s1, int pos1, string s2, int pos2)
{
    if (pos1 == s1.size())
    {
        cout << pre << s2.substr(pos2) << endl;
        return;
    }
    if (pos2 == s2.size())
    {
        cout << pre << s1.substr(pos1) << endl;
        return;
    }
    string pre1 = pre + s1.substr(pos1, 1);
    string pre2 = pre + s2.substr(pos2, 1);
    interleavings(pre1, s1, pos1 + 1, s2, pos2);
    interleavings(pre2, s1, pos1, s2, pos2 + 1);
}

int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    interleavings("", s1, 0, s2, 0);
    return 0;
}

Could someone please explain an algorithm of what they have implemented. Figuring from code is exceedingly difficult.

#include <iostream>
using namespace std;

void interleavings(string pre, string s1, int pos1, string s2, int pos2)
{
    if (pos1 == s1.size())
    {
        cout << pre << s2.substr(pos2) << endl;
        return;
    }
    if (pos2 == s2.size())
    {
        cout << pre << s1.substr(pos1) << endl;
        return;
    }
    string pre1 = pre + s1.substr(pos1, 1);
    string pre2 = pre + s2.substr(pos2, 1);
    interleavings(pre1, s1, pos1 + 1, s2, pos2);
    interleavings(pre2, s1, pos1, s2, pos2 + 1);
}

int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    interleavings("", s1, 0, s2, 0);
    return 0;
}

Basically in every recursion, you have two choices, pick the first character of string A or that of string B. A and B are given input strings for first iteration of recursion and for making further calls we pass A+1 if we chose the character from A and so for B.
Following is compilable C++ code, though you might have to set the size of r to sizeof(a)+sizeof(b).

#include <iostream>
using namespace std;

void interleave(char a[], char b[], char r[], int len){
    if(a[0]=='\0' && b[0]=='\0') {
        cout<<r<<endl;
        return;
    }
    if(a[0]!='\0') {
        r[len]=a[0];
        interleave(a+1, b,r,len+1);
        r[len]='\0';
    }
    if(b[0]!='\0') {
        r[len]=b[0];
        interleave(a, b+1,r,len+1);
        r[len]='\0';
    }
}


int main(int argc, const char * argv[]){
    char a[]={'A','B','\0'};
    char b[]={'C','D','E','\0'};
    char r[10];
    r[0]='\0';
    interleave(a, b, r, 0);
    return 0;
}

public void interleave(String a, String b) {
		interleave(a, b, 0, 0, 0, new char[a.length() + b.length()]);
	}

	private void interleave(String a, String b, int indA, int indB,
			int current, char[] newWord) {

		if (current == newWord.length) {
			System.out.println(newWord);
			return;
		}
		if (indA < a.length()) {
			newWord[current] = a.charAt(indA);
			interleave(a, b, indA + 1, indB, current + 1, newWord);
		}

		if (indB < b.length()) {
			newWord[current] = b.charAt(indB);
			interleave(a, b, indA, indB + 1, current + 1, newWord);
		}
	}

Here is running C Program

#include <stdio.h>
#include <string.h>
#include <stdarg.h>
#include <stdlib.h>

void intliv_two_strings(char *str1, char *str2, char *res_str, int index);
int count = 0;
int main()
{
	char str1[] = "ABCD", str2[] = "EFGH";
	int index = strlen(str1) + strlen(str2);
	char res_str[index];
        count = 0;
	memset(res_str, 0, index);
	intliv_two_strings(str1, str2, res_str, 0);
        printf("Total number of generated string: %d\n", count);
	return 0;
}

void intliv_two_strings(char *str1, char *str2, char *res_str, int i)
{
	int l1 = strlen(str1), l2 = strlen(str2);
        char str1_t[10], str2_t[10];
        int k = strlen(res_str);
        strcpy(str1_t, str1);
        strcpy(str2_t, str2);

	if(l1 == 0 && l2 == 0) {
            return;
	} else if(l1 == 0) {
		printf("%s",str2);
                for(k; k>0; k--)
                    printf("%c", res_str[k-1]);
                printf("\n");
                count++;
		return;
	} else if (l2 == 0) {
		printf("%s",str1);
                for(k; k>0; k--)
                    printf("%c", res_str[k-1]);
                printf("\n");
                count++;
		return;
	} else {
		res_str[i] = str1[l1-1]; res_str[i+1] = '\0';
		str1_t[l1-1] = '\0';
		intliv_two_strings(str1_t, str2, res_str, i+1);

		res_str[i] = str2[l2-1]; res_str[i+1] = '\0';
		str2_t[l2-1] = '\0';
		intliv_two_strings(str1, str2_t, res_str, i+1);
	}
}

char* interleaveStrings(char* str1, char* str2, char[] result, int i) {
   if (*str1 == '\0' and *str2 == '\0') {
   	printf(result);
   }
   else if (*str1 == '/0') {
   	result[i] = *str2;
   	interleaveStrings(str1, str2++, result, i+1);
   }
   else if (*str2 == '/0') {
   	result[i] = *str1;
   	interleaveStrings(str1++, str2, result, i+1);
   }
   else {
   	result[i] = *str2;
   	interleaveStrings(str1, str2++, result, i+1);
   	result[i] = *str1;
   	interleaveStrings(str1++, str2, result, i+1);
   }
}

void main() {
char* str1 = "asdf";
char* str2 = "qwerty";
char result[10];
interleaveStrings(str1, str2, result, 0);
}

plz giv pseudo code..

#include <iostream>
#include <stdio.h>
using namespace std;

void FindInterleaving(char* cResult, int nResult, char *cSt1,char *cSt2){
        if(*cSt1=='\0' && *cSt2=='\0')
                return ;
        if(*cSt1=='\0'){
                while(*cSt2!='\0'){
                        cResult[nResult++]=*cSt2;
                        cSt2++;
                }
                cResult[nResult]='\0';
                printf("%s\n",cResult);
                return ;

        }

        if(*cSt2=='\0'){
                while(*cSt1!='\0'){
                        cResult[nResult++]=*cSt1;
                        cSt1++;
                }
                cResult[nResult]='\0';
                printf("%s\n",cResult);
                return ;

        }

        cResult[nResult++]=*cSt1;
        FindInterleaving(cResult,nResult,cSt1+1,cSt2);

        cResult[nResult-1]=*cSt2;
        FindInterleaving(cResult,nResult,cSt1,cSt2+1);


}


int main(){
char cSt1[3]="AB",cSt2[3]="CD";
char *cResult= new char[5];
int nResult=0;
FindInterleaving(cResult,nResult,cSt1,cSt2);


}

public class InterleaveString {
  public static void printInterleaving(String s1, String s2, String s){
    if(!s1.isEmpty())
      printInterleaving(s1.substring(1), s2,s+s1.charAt(0));
    if(!s2.isEmpty())
      printInterleaving(s1, s2.substring(1), s+s2.charAt(0));
    if(s1.isEmpty() && s2.isEmpty())
      System.out.println(s);
  }
  public static void main(String[] args) {
    String s1 = "AB";
    String s2 = "CD";
    printInterleaving(s1,s2,"");
  }
}

Public InterLeavedStrings() As String
    Public Counts As Integer

    Public Sub Main(ByVal String1 As String, ByVal String2 As String)
        GetInterleaveStrings(String1, String2)
        Counts += 2
        ReDim Preserve InterLeavedStrings(Counts)
        InterLeavedStrings(Counts) = String1 + String2
        InterLeavedStrings(Counts) = String2 + String1
        GetInterleaveStrings(String2, String1)
        


    End Sub
    Public Sub GetInterleaveStrings(ByVal string1 As String, ByVal string2 As String)
        Dim TempString1 As String
        Dim TempSecondString As String

        Dim TempString2 As String
        Dim TempSecondString2 As String

        Dim TempString3 As String
        Dim TempSecondString3 As String

        For I As Integer = 0 To string1.Length - 1
            TempString1 = string1.Substring(0, I + 1)
            TempSecondString = string1.Substring(I + 1, string1.Length - I - 1)
            For k As Integer = 0 To string2.Length - 1
                TempString2 = string2.Substring(0, k + 1)
                TempString2 = TempString2 + TempString1

                TempSecondString2 = string2.Substring(k + 1, string2.Length - k - 1)
                For j As Integer = 0 To TempSecondString2.Length - 1
                    TempString3 = TempSecondString2.Substring(0, j + 1)
                    TempSecondString3 = TempSecondString2.Substring(j + 1, TempSecondString2.Length - j - 1)
                    TempString3 = TempString2 + TempString3 + TempSecondString + TempSecondString3
                    Counts += 1
                    ReDim Preserve InterLeavedStrings(Counts)
                    InterLeavedStrings(Counts) = TempString3
                    If TempSecondString = "" Then Exit For
                Next
                If TempSecondString2 = "" Then Exit For

            Next
            If TempSecondString = "" Then Exit For
        Next


    End Sub

Really easy solution using next_permutation:

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
void interleaveStrings(const string &s1, const string &s2) {
  size_t len1 = s1.length(), len2 = s2.length();
  vector<char> v(len1 + len2);
  fill(v.begin() + len1, v.end(), (char)1);
  do {
    for (size_t i = 0, p1 = 0, p2 = 0; i < len1 + len2; ++i) {
      if (v[i])
        cout << s1[p1++];
      else
        cout << s2[p2++];
    }
    cout << endl;
  } while (next_permutation(v.begin(), v.end()));
}

public void interleave(String ab, String cd, String str) {
		if(ab.length() == 0) {
			str += cd;
			System.out.println(str);
			return;
		}

		//string start with A
		interleave(ab.substring(1), cd, str + ab.charAt(0));

		//string start with C
		interleave(cd.substring(1), ab, str + cd.charAt(0));

	}

This is my answer. I consider recursion as the best way to solve it.

#include <iostream>
using namespace std;


void solve(char *x,char *y,char *z,int dep,int len){
if(dep==len){
z[dep]='\0';
printf("%s\n",z);
return ;
}
if(*x!='\0'){
z[dep]=*x;
solve(x+1,y,z,dep+1,len);
}
if(*y!='\0'){
z[dep]=*y;
solve(x,y+1,z,dep+1,len);
}
}
int main(){
char x[105],y[105],z[205];
scanf("%s",x);
scanf("%s",y);
solve(x,y,z,0,strlen(x)+strlen(y));
return 0;
}

void interleaving(char* s1,char* s2,char* res,int depth)
{
        if(!*s1 && !*s2)
        {
                res[depth]='\0';
                printf("%s\n",res);
        }
        if(*s1)
        {
                res[depth]=*s1;
                interleaving(s1+1,s2,res,depth+1);
        }
        if(*s2)
        {
                res[depth]=*s2;
                interleaving(s1,s2+1,res,depth+1);
        }
}

Complete code: ideone.com/35VNh

public class Interleave {
public static void interleave(String a, String b) {
interleave("", a, 0, b, 0);
}

public static void interleave(String result, String a, int idxA, String b, int idxB) {
if (result.length() == a.length() + b.length()) {
System.out.println(result);
return;
}

if (idxA < a.length()) {
interleave(result + a.charAt(idxA), a, idxA + 1, b, idxB);
}

if (idxB < b.length()) {
interleave(result + b.charAt(idxB), a, idxA, b, idxB + 1);
}
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

interleave("ABC", "DE");
}

#include<stdio.h>
#include<conio.h>
#include<string.h>
main()
{
char str[100];
char temp;
int i,j,l,k;
char str1[]="AB";
gets(str);
//printf("%s\n",str);
l=strlen(str)+strlen(str1);
char str2[100],str3[100];
for(i=0;i<l-1;i++)
{
for(j=0;j<i;j++)
{
str2[j]=str[j];
}
str2[i]='A';
for(j=l-2;j>i;j--)
{
str2[j]=str[j-1];
}
str2[l-2+1]='\0';
//printf("%s\n",str2);
for(j=i+1;j<l;j++)
{
for(k=0;k<j;k++)
{
str3[k]=str2[k];
}
str3[j]='B';
for(k=l-1;k>j;k--)
{
str3[k]=str2[k-1];
}
str3[l]='\0';

printf("%s\n",str3);
}

}
//printf("%d",count);
//printf("%s\n",str);
getch();
}

Simple Implementation in java:-

package google;

import java.util.HashSet;
import java.util.Set;



public class InterleavingWords {
static int count = 0;
static Set<String> setOfString = new HashSet<String>();
static Set<String> set = new HashSet<String>();

public static void main(String[] args) {
String str1 = "abc";
String str2 = "def";
char[] charArray1 = str1.toCharArray();
char[] charArray2 = str2.toCharArray();
char[] out = new char[charArray1.length + charArray2.length];
interleavingSrings(charArray1, charArray2, out, 0, 0, 0);
System.out.println(count);
}

private static void interleavingSrings(char[] charArray1,
char[] charArray2, char[] out, int i, int j, int k) {

if(k == out.length){
System.out.println(out);
k = 0;
count++;
System.out.println(" Not a Duplicate Element : " + set.add(String.valueOf(out)));
}else{
for(int t = i; t < charArray1.length; t++){
out[k] = charArray1[t];
interleavingSrings(charArray1,charArray2, out, t+1, j, k+1);
}

for(int l = j; l < charArray2.length; l++){
out[k] = charArray2[l];
interleavingSrings(charArray1, charArray2, out, i, l + 1, k+1);
}

}
}
}

cool recursion indeed, I did not know this!
Here's my code:

void private_interleave ( const std::string& prefix, const std::string& s1, const std::string& s2 )
{
    if ( s1.size() == 0 || s2.size() == 0 )
    {
        std::cout << prefix+s1+s2 << std::endl;
        return;
    }
    private_interleave ( prefix + s1.substr ( 0,1 ),s1.substr ( 1 ), s2 );
    private_interleave ( prefix + s2.substr ( 0,1 ),s1, s2.substr ( 1 ) );
}

void public_interleave ( const std::string& input1, const std::string& input2 )
{
    private_interleave ( "", input1, input2 );
}

but to improve speed we can at least avoid to copy substrings, like so:

void print_interleaving(const std::string& prefix,
                        uint prefix_size,
                        const std::string& s1,
                        uint start1,
                        uint end1,
                        const std::string& s2,
                        uint start2,
                        uint end2)
{
    int i;
    for (i=0;i<prefix_size;i++)
        std::cout << prefix[i];
    for (i=start1;i<=end1;i++)
        std::cout << s1[i];
    for (i=start2;i<=end2;i++)
        std::cout << s2[i];
    std::cout << std::endl;
}

void private_interleave_opt ( std::string& prefix,
                              uint prefix_size,
                              const std::string& s1,
                              uint start1,
                              uint end1,
                              const std::string& s2,
                              uint start2,
                              uint end2 )
{
    if ( end1<start1 || end2<start2 )
    {
        print_interleaving (prefix,prefix_size,s1,start1,end1,s2,start2,end2);
        return;
    }
    
    prefix[prefix_size] = s1[start1];  
    private_interleave_opt ( prefix , prefix_size+1, s1, start1+1, end1, s2, start2, end2 );
    
    prefix[prefix_size] = s2[start2];   
    private_interleave_opt ( prefix , prefix_size+1, s1, start1, end1, s2, start2+1, end2 );
}

void public_interleave_opt ( const std::string& input1, const std::string& input2 )
{
    std::string prefix;
    prefix.resize ( std::max ( input1.size(), input2.size() ) );
    private_interleave_opt ( prefix,0, input1,0,input1.size()-1, input2,0,input2.size()-1 );
}

# include <stdio.h>
# include <stdlib.h>
# include <cstdio>
# include <string>

using namespace std;

char *a,*b,*op;
int len_a,len_b,len_op;

void f(int i,int j,int k){
	char c;
	if(i == -1){
		c = b[j+1];
		b[j+1] = 0;
		printf("%s%s\n",b,op+k);
		b[j+1] = c;
	}
	else if(j == -1){
		c = a[i+1];
		a[i+1] = 0;
		printf("%s%s\n",a,op+k);
		a[i+1] = c;
	}
	else{
		op[k-1] = a[i];
		f(i-1,j,k-1);
		op[k-1] = b[j];
		f(i,j-1,k-1);
	}
	return;
}

int main ()
{
	a = (char *)calloc(20,sizeof(char));
	b = (char *)calloc(20,sizeof(char));
	scanf("%s\n",a);
	scanf("%s\n",b);
	len_a = strlen(a);
	len_b = strlen(b);
	op = (char *)calloc((len_a+len_b+2),sizeof(char));
	f(len_a-1,len_b-1,len_a+len_b);

	return 0;
}

Here is tha algo:

2 strings are say A and B..take two pointer, pointer1 for A,pointer2 for B.

For getting all possible interleavings, we gave two choices,

either take char pointed by pointer1 and advance pointer1
or, take char pointed by pointer2 and advance pointer2.

We can not advance the pointers further if the corresponding string's end is reached...

So here is my code:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void interleaving(char *a,char *b,int s1,int s2,int e1,int e2,char *c,int index){
	if(s1<=e1&&s2<=e2){
		c[index]=a[s1];
		interleaving(a,b,s1+1,s2,e1,e2,c,index+1);
		c[index]=b[s2];
		interleaving(a,b,s1,s2+1,e1,e2,c,index+1);		
	}
	else if(s1<=e1){
		c[index]=a[s1];
		interleaving(a,b,s1+1,s2,e1,e2,c,index+1);
	}
	else if(s2<=e2){
		c[index]=b[s2];
		interleaving(a,b,s1,s2+1,e1,e2,c,index+1);
	}
	else{
		int i;
		for(i=0;i<index;i++){
			printf("%c",c[i]);
		}
		printf("\n");
	}
}		
		
main(){
	char a[10],b[10],c[20];
	gets(a);
	gets(b);
	int start1=0,start2=0,end1,end2;
	end1=strlen(a)-1;
	end2=strlen(b)-1;
	interleaving(a,b,start1,start2,end1,end2,c,0);
}

string substring(string s){ //removes first char from string and returns the rest
    string s_="" ;
    for(int i(1);i<s.length(); i++){
        s_+= s[i];
    }
    return s_;
}
void interleaving(string printed, string a, string b){
    if (a=="") cout<<printed<<b<<endl;
    else if (b=="") cout<<printed<<a<<endl;
    else {
        string p = printed+a[0];
        interleaving(p, substring(a),b);
        p = printed+b[0];
        interleaving(p, a,substring(b));
    }
}

Recursion is the easiest to implement

void interleavings (const std::string & s1, const std::string & s2, std::vector<std::string> & v)
{
	if (s1.empty ())
	{
		v.push_back (s2);
		return;
	}

	if (s2.empty ())
	{
		v.push_back (s1);
		return;
	}

	std::vector<std::string> v1;
	interleavings (s1.substr (1), s2, v1);
	for (int i = 0; i < v1.size (); ++i)
	{
		v.push_back (s1.substr (0, 1) + v1.at (i));
	}

	std::vector<std::string> v2;
	interleavings (s1, s2.substr (1), v2);
	for (int i = 0; i < v2.size (); ++i)
	{
		v.push_back (s2.substr (0, 1) + v2.at (i));
	}
}

However, if the given strings are big enough one will have to use the iterative implementation. I suspect that will probably be the follow up in the interview anyway.

Good one

printInterleavingsSorted("ab".toCharArray(), "cd".toCharArray(), "", 0, 0);

	private static void printInterleavingsSorted(char[] c1, char[] c2, String prefix, int i, int j) {
		if (i == c1.length) {
			System.out.println(prefix + new String(c2, j, c2.length - j));
			return;
		}
		if (j == c2.length) {
			System.out.println(prefix + new String(c1, i, c1.length - i));
			return;
		}
		if (c1[i] <= c2[j]) {
			printInterleavingsSorted(c1, c2, prefix + c1[i], i + 1, j);
			printInterleavingsSorted(c1, c2, prefix + c2[j], i, j + 1);
		} else {
			printInterleavingsSorted(c1, c2, prefix + c2[j], i, j + 1);
			printInterleavingsSorted(c1, c2, prefix + c1[i], i + 1, j);			
		}
	}

vector<string> get_interleavings(const string s1, const string s2)
{
	vector<string> vec;
	if(s1.length() > 0)
	{
		char first = s1[0];
		vector<string> temp = get_interleavings(s1.substr(1, s1.length() - 1), s2);
		for(size_t i = 0; i < temp.size(); ++i)
		{
			vec.push_back(first + temp[i]);
		}
	}

	if(s2.length() > 0)
	{
		char first = s2[0];
		vector<string> temp = get_interleavings(s2.substr(1, s2.length() - 1), s1);
		for(size_t i = 0; i < temp.size(); ++i)
		{
			vec.push_back(first + temp[i]);
		}
	}

	return vec;
}

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

void findInterleaves(const string &a, const string &b, string c, int indA, int indB) {
     if(indA == a.length() && indB == b.length()) {
        std::cout << c << std::endl;
        return;
     }       
     if(indA < a.length()) 
        findInterleaves(a, b, c+a[indA], indA+1, indB);  
                
     if(indB  < b.length())
        findInterleaves(a, b, c+b[indB], indA, indB+1);  
               
}

int main(int argc, char *argv[])
{
    std::string str("");
    findInterleaves("AB","CD", str, 0, 0);
    system("PAUSE");
    return EXIT_SUCCESS;

}

#include <string>
#include <iostream>
using namespace std;

void interleave(const string &a, const string &b, const string &prefix = string()) {
    if (!a.empty())
        interleave(a.substr(1), b, prefix + a.substr(0, 1));
    if (!b.empty())
        interleave(a, b.substr(1), prefix + b.substr(0, 1));
    if (a.empty() && b.empty())
        cout << prefix << "\n";
}

int main() {
    interleave("AB", "CD");
}

public class Test {
	
	public void DFS(String s1, String s2,String out1,int index1,int index2) {
		if (index1 + index2 >= s1.length()+s2.length() ) {
			System.out.println(out1);
			return;
		}
		if (index1 >= s1.length()) {
			DFS(s1,s2,out1 + s2.toCharArray()[index2], index1,index2+1);
		} else if (index2 >= s2.length() ) {
			DFS(s1,s2,out1 + s1.toCharArray()[index1], index1+1,index2);
		} else {
			DFS(s1,s2,out1 + s1.toCharArray()[index1], index1+1,index2);
			DFS(s1,s2,out1 + s2.toCharArray()[index2], index1,index2+1);
		}
		
	}
	
	public static void main(String args[]) {
		new Test().DFS("AB","CD","",0,0);
	}
}

Solution in Groovy with unit test

def "should calculate all the intervealed string of 'AB' and 'CD'"() {
	expect:
	intervealedStrings("AB", "CD") == ["ABCD", "ACBD", "ACDB", "CABD", "CADB", "CDAB"]
}
	

public List<String> intervealedStrings(String str1, String str2) {
	List<String> result = new ArrayList<String>();
	char[] s = new char[str1.length() + str2.length()];	
	intervealedPermutations(result, str1, str2, 0, 0, s, 0);
	
	return result;
}
		

public void intervealedPermutations(List<String> result, String str1, String str2, int next1, int next2, char[] s, int i) {		
	if(next1 == str1.length() && next2 == str2.length()) {
		result.add(new String(s));
	}

	if(next1 < str1.length()) {
		s[i] = str1.charAt(next1);
		intervealedPermutations(result, str1, str2, next1+1, next2, s, i+1);
	}

	if(next2 < str2.length()) {
		s[i] = str2.charAt(next2);
		intervealedPermutations(result, str1, str2, next1, next2+1, s, i+1);
	}
}

If string1 has size m and string2 has size n, how many strings are generated?

Let the first string be of length n and second string of length m. Then find all the combinations of choosing n numbers form (n+m). Put first string in those places in order and then put the second string in rest of the places in order. Now the question comes out to be choosing some r object from n object. Of course you have to code it.