Given string is interleaving of two other strings or not

StringViews 1749

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.


a) Input strings :

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.


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

Try It



Translate »