**Description: We have to check whether a given string S is an interleaving of 2 other strings S1 and S2. A string S is said to be an interleaving of S1 and S2 is it contains all characters of S1 and S2 and order of characters in individual strings is preserved.**

**Example:**

**Input:**

S1:”cat”

S2:”dog”

S: ”cdatog ”

**Output:**

Interleaving is present.

**Algorithm:**

1.Intialize variables ‘i’(index for S1), ‘j’(index for S2) and ‘k’(Index for S) as 0.

2.Scan through the string S using index ‘k’ and check following conditions:

-If the value of S[k] is equal to S1[i] and the value of ‘i’ is less than the length of the string S1, increment ‘i’ by 1.

-Else If, the value of S[k] is equal to S2[j] and the value of ‘j’ is less than the length of the string S2, increment ‘j’ by 1.

-Else, break out of the loop as NO INTERLEAVING is present.

3.If the 2^{nd} step gives positive results, check if

Length(S1) +Length(S2)==Length(S)

If equal, INTERLEAVING IS PRESENT.

**Implementation in C:**

/* The following function returns 1 if S is an interleaving of S1 and S2, else returns 0*/

int check_interleaved (char *S1, char *S2, char *S)

{

/*Loop through all characters of S.*/

while (*S != 0)

{

/*Match first character of S with first character of S1*/

if (*S1 == *S)

S1++;

/*Match first character of S with first character of S2*/

else if (*S2 == *S)

S2++;

else

return 0;

/*move S to next*/

S++;

}

/*If S1 or S2 still have some characters, then length of S is smaller than sum of lengths of S1 and S2, so return 0.*/

if (*S1 || *S2)

return 0;

return 1;

}

**Note:** The above method fails if S1 and S2 have some characters in common. For example, if string S1 = “AAB”, string S2 = “AAC” and string S = “AACAAB”, then the above method will return false.