Pragya and Gold Medalist

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:

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

Previous post Print the Pattern
Next post Sum of Sequence

Leave a Reply

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