Check if string is interleaved of two strings

Given three strings A,B and C, find if C string is interleaved of two strings. A and B. C is said to be interleaved if it contains all the characters of A and B and order of characters in respective strings is maintained. For example string C in figure is interleaved string of A and B.

check string is interleaved of two strings

Find if string is interleaved of two strings

Simple algorithm to find if a string is interleaved of two other string is to start checking length of C as length of A + length of B. If it is not true return false (why?).

If length criteria passes, check first character of C and A. If they match, move to second character of C and A. Keep B at first character. If character in A does not match with character in C, check if first character of C and B match, if they do, then move to second character of C and B. A remains at first character.

Once done, repeat above steps with next characters of strings, while character in C matches character in A or B. If both current character in C does not match with any of the current characters in A and B, return false.

With above algorithm, with each comparison, problem reduces to smaller size, with C with length N-1, one of A or B with M-1. From the description, it is clear that recursion can be used to solve interleaving problem.

isInterleaved(A,B,C)  = isInterleaved(A+1, B, C+1) 
                        || isInterleaved(A, B+1,C+1)

What shall be base case for above recursion?
If end of C is reached, all characters in C are checked, return true if all characters in other two strings are also considered. If not returned false.
Other way, if both string are A and B are fully considered and there are still characters left in C to be considered, then return false. (This case is anyways caught at length check).

Recursive Implementation of interleaved strings algorithm


#include <stdio.h>
#include <string.h>
#define true 1
#define false 0; 
 
int isInterleaved(char *c, char *a, char *b){
 
    if(!(*c) && !(*a) && !(*b))
        return true;
 
    if(*c == '\0'){
        return false;
    }
	 // if character of a and c match
    return ((*c == *a) && isInterleaved(c+1,a+1,b)) || 
    		// if character of b and c match
            ((*c == *b) && isInterleaved(c+1,a,b+1)); 
}
 
int main(void) {
	char *c = "abxycdz";
	char *a = "abcd";
	char *b = "xyz";
	if(isInterleaved(c,a,b)){
	    printf("\n String is interleaved");
	}
	else{
	    printf("\n String is not interleaved");
	}
	return 0;
}

Iterative implementation is as follows

#include <stdio.h>
#include <string.h>
#define true 1
#define false 0; 
 
int isInterleaved(char *c, char *a, char *b){
 
    while(*c != '\0'){
    	if(*c == *a){
            a++;
        }
        else if(*c == *b){
            b++;
        }
        else{
            return false;
        }
        c++;
    }
    if(*a != '\0' || b != '\0')
        return false;
 
    return true;
}
 
int main(void) {
	// your code goes here
	char *c = "abxycdz";
	char *a = "abcd";
	char *b = "xyz";
	if(isInterleaved(c,a,b)){
		printf("\n String is interleaved");
	}
	else{
		printf("\n String is not interleaved");
	}
	return 0;
}

Iterative implementation will not work with input with common characters in string A and B, for example A = XXY and B = XXZ and if C = XXZXXY will return false.

Complexity of iterative implementation will be linear O(N), N being length of string C, where as complexity of recursive solution will b O(2N) but it does not fail in when two strings have common character.

Dynamic programming approach to interleaved strings problem

Look closely and notice that many subproblems are being calculated again and again. Recursion tree for input A = XXY and B = XXZ and C = XXZXXY

interleaved strings with dynamic programming

Looking at the recursion tree, it is clear that if results of subproblems are stored, they need not be calculated again and again. Create a two dimensional table. Table(i,j) = true only if C[i+j-1] is interleaved string if A[i] and B[j]. Empty string is interleaved of two other strings so, Table[0][0] = true
If one of the strings was empty: Table(i,0) = A[i] == C[i] && Table(i-1, 0) that is to say if till i-1 characters C was interleaved of A, then for ith character it will be true if ith character matches ith character of A. Note that B is empty. Again if string A is empty, then Table(0,j) = Table(0, j-1). With these base cases, we can fill table bottom up as follows

Table(i,j) = Table(i-1,j)  if (A[i] == C[i+j]) && (B[j] != C[i+j])
Table(i,j) = Table(i,j-1) (B[i] == C[i+j])&& (A[i] != C[i+j])
Table(i,j) = Table(i-1,j) || Table(i, j-1) if (A[i] == C[i+j]) && (B[j] == C[i+j])

Dynamic programming solution to find if string is interleaved of two strings

#include <stdio.h>
#include <string.h>
#define true 1
#define false 0; 
int isInterleaved(char *c, char *a, char *b){
 
    int lenA = strlen(a);
    int lenB = strlen(b);
    int i,j;
 
    int Table[lenA+1][lenB+1];
    // Initialization
	for(i=0; i<=lenA; i++){
        for(j=0; j<=lenB; j++){
        	Table[i][j] = false;
        }
	}
    for(i=0; i<=lenA; i++){
        for(j=0; j<=lenB; j++){
        	// Both strings are empty
            if(i==0 && j==0)
                Table[i][j] = true;
    		// string A is empty, compare characters in C and B
            if(i==0 && c[j-1] == b[j-1]){
                Table[i][j] =  Table[i][j-1];
            }
            // string B is empty, compare characters in C and A
	        else if(j==0 && c[i-1] == a[i-1]){
                Table[i][j] =  Table[i-1][j];
            }
            // Both strings are not empty
            //1. If character of A matches with character of C
            // but not of B
            else if (a[i-1] == c[i+j-1] && b[j-1] != c[i+j-1]){
                Table[i][j] = Table[i-1][j];
            }
            //2. If character of B matches with character of C
            // but not of A
            else if (a[i-1] != c[i+j-1] && b[j-1] == c[i+j-1]){
                Table[i][j] = Table[i][j-1];
            }
            //1. If character of A matches with character of C
            // and character of B also matches with C
            else if (a[i-1] == c[i+j-1] && b[j-1] == c[i+j-1]){
                Table[i][j] = Table[i-1][j] || Table[i][j-1];
            }
        }
    }
    return Table[lenA][lenB];
}
 
int main(void) {
	// your code goes here
	char *c = "abxycdz";
	char *a = "abcd";
	char *b = "xyz";
	if(isInterleaved(c,a,b)){
		printf("\n String is interleaved");
	}
	else{
		printf("\n String is not interleaved");
	}
	return 0;
}

Complexity of dynamic programming algorithm to find if a string is interleaved of two strings will be O(n2).

For more dynamic programming problems, please refer : Dynamic programming problems

Please share if there is something wrong or missing. We would love to hear what you have to say. If you are interested in contribute to website, please contact us.

  • Ankit Tripathi

    Thanks for the explanation.
    EDIT: Table(i,j) = Table(i,j-1) (B[i] == C[i+j])&& (A[j] != C[i+j])
    Should be : Table(i,j) = Table(i,j-1) (B[j] == C[i+j])&& (A[i] != C[i+j])

    • http://algorithmsandme.in/ Jitendra Sangar

      Thanks for pointing out. Corrected it,