# Pragya and Gold Medalist ### CONCEPTS USED:

Recursion

Medium

#### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given two strings `S1` and `S2`, print the count of all their `Interleaving Strings`.
NOTE:

1. `Interleaving String` is a string that has the same order that of individual strings. This property should be maintained in the `Interleaving Strings` of `S1` and `S2`.
1. And all characters from `S1` and `S2` should be present in their `Interleaving Strings`.

#### For Example:

``````Input : ab cd

Output : 6

Explanation :  [abcd, acbd, acdb, cabd, cadb, cdab]

All these are valid Interleaving Strings because original order is preserved in each and every string.

While [abdc, bacd, bcda, adcb] are some of the non-interleaving strings.``````

See original problem statement here

Can we use `Recursion` here ?

Yes, `Recursion` seem to be a great option whenever we need to find different combinations.

#### SOLVING APPROACH:

1. Initialize an empty string `str` and recursively keep adding characters one after the other either from the first string or the other string till both the strings become exhausted.

2. This is done recursively, where choosing a character from both the strings can be done in `2` ways, so it takes `Exponential Time Complexity`.

#### SOLUTIONS:

```#include <stdio.h>
int cnt ;
//Function for counting all interleavings
void countIlsRecur (int m,int n){
/* Base case: If all characters of str1 and str2 have been
included in output string, then print the output string */
if (m == 0 && n == 0){
//cout << iStr << endl;
cnt++;
}
/* If some characters of str1 are left to be included, then
include the first character from the remaining characters
and recur for rest */
if (m > 0)  {
//iStr[i] = str1;
countIlsRecur (m - 1, n);
}
/* If some characters of str2 are left to be included, then
include the first character from the remaining characters
and recur for rest */
if (n > 0)  {
//iStr[i] = str2;
countIlsRecur(m,n - 1);
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
char str1,str2;
scanf("%s",str1);
scanf("%s",str2);
countIlsRecur(strlen(str1),strlen(str2));
printf("%d\n",cnt);
cnt = 0;
}
return 0;
}
```
```#include <bits/stdc++.h>
using namespace std;
int countt = 0;
void interleaving(int a,int b){
/* If some characters of s1 are left to be included, then
include the first character from the remaining characters
and recur for rest  */
if(a > 0){
interleaving(a-1,b);
}
/* If some characters of s2 are left to be included, then
include the first character from the remaining characters
and recur for rest  */
if(b > 0){
interleaving(a,b-1);
}
/* Base case: If all characters of s1 and s2 have been
included in output string */
if(a == 0 && b == 0){
countt++;
}
}
int main(){
int t;cin>>t;
while(t--){
string s1,s2;
cin>>s1>>s2;
int l1 = s1.size();
int l2 = s2.size();
interleaving(l1,l2);
cout<<countt<<"\n";
countt=0;
}
return 0;
}
```
```import java.util.*;
import java.io.*;

public class Main {

public static int countt = 0;

static void interleaving(int a,int b){
/* If some characters of s1 are left to be included, then
include the first character from the remaining characters
and recur for rest  */
if(a > 0){
interleaving(a-1,b);
}
/* If some characters of s2 are left to be included, then
include the first character from the remaining characters
and recur for rest  */
if(b > 0){
interleaving(a,b-1);
}
/* Base case: If all characters of s1 and s2 have been
included in output string */
if(a == 0 && b == 0){
countt++;
}
}
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t!=0){
String s1 = sc.next();
String s2 = sc.next();
int l1 = s1.length();
int l2 = s2.length();
interleaving(l1,l2);
System.out.println(countt);
countt=0;
t--;
}
}
}
```
```countt = 0
def interleaving( a, b):
global countt
if(a > 0):
interleaving(a - 1, b)

if(b > 0):
interleaving(a, b - 1)

if(a == 0 and b == 0):
countt += 1

for _ in range(int(input())):

s1, s2 = input().split()
l1, l2 = len(s1), len(s2)
interleaving(l1, l2)
print(countt)
countt = 0
```

[forminator_quiz id="986"]

This article tried to discuss the concept of Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion you can check out MYCODE | Competitive Programming.