Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Pragya and Gold Medalist

Last Updated on March 28, 2022 by Ria Pathak

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.

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[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--;
    }
  }
}
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.

Leave a Reply

Your email address will not be published. Required fields are marked *