Home Â» Technical Interview Questions Â» String Interview Questions Â» Given string is interleaving of two other strings or not

# Given string is interleaving of two other strings or not

String

## Write a function to find if a given string C is interleaving of other two given strings A and B.

Interleaving : C is said to be interleaving of A and B, if it contains all characters of A and B, order of all characters in individual strings (A, B) is preserved.

### Examples

a) Input strings :

A : ACBD
B : AB
C : CD

Output : True

b) Input strings:

B : AB
C : CD

Output : False, even though all characters are there, order is changed.

Time complexity : O(m+n), m and n are lengths of strings.

## Algorithm

Given strings be A, B and C, Check if C is interleaving of A and B

1. Iterate through all characters of C, pick characters of C one by one.

2. If it doesnâ€™t matches with first character of A and B then return False.

3. If the character matches with first character of A, repeat above process for second character of C. compare with second character of A and first of B.

4. Continue this process till it reaches the last character of A.

5. If all characters matches either with a character of A or character of B and length of C is sum of length of A and length of B.

6. Return True.

## C++ Program

```#include <bits/stdc++.h>

using namespace std;

//Main function to check
int main()
{
const char *A = "CBD";
const char *B = "AGH";
const char *C = "ACGHBD";
//For all charcters in C
while (*C != 0)
{
//If charcter is equal to charcter in A
if (*A == *C)
{
A++;//Increment A pointer, next charcter
}
//If charcter is equal to charcter in B
else if (*B == *C)
{
B++;//Increment B pointer, next character
}
//If charcter is not equal to charcter in A and B
else
{
cout<<"not an interleaving"<<endl;//return false
}
C++;//Increment C pointer, next character
}
//After finishing all characters in C
//Characters still left in A or B, Then return false
if (*A || *B)
{
cout<<"not an interleaving"<<endl;;
}
//Else return true
cout<<"ACGHBD is an interleaving of CBD and AGH"<<endl;
return 0;
}```

READ  Arrange given numbers to form the biggest number

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions