#### CONCEPTS USED:

Recursion

#### DIFFICULTY LEVEL:

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 according to the fundamentals of data structures in c++.

#### SOLVING APPROACH:

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.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[0]; 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[0]; countIlsRecur(m,n - 1); } } int main(){ int t; scanf("%d",&t); while(t--){ char str1[100],str2[100]; 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--; } } }