CareerCup

After reading through a bunch of these "solutions", I realized there are 3 common mistakes people make. You might want to make sure that none of these applies to your solution before posting it.

(1) Order is important. In other words, you can't just check whether A & B form an anagram of C
(2) If the next character in A & B both match that of C, you can't just automatically advance the position in either A or B and move on. Consider A="ca" and B="cb". Your solution should return true for both C="cacb" and C="cbca".
(3) If the next character in A & B both match that of C, you can't just insert this character into a queue and try to use it up, then advance the position in both A & B. Consider A="ca", B="cb" and C="cabc". If you insert 'c' into the queue and advance the position in both A & B, you will be able to match the subsequent 'a' and 'b' incorrectly.

My code is as follows, it passes LeetCode online judge.
The code can be optimized by putting more work done in recursive calls. I choose to write more code and invoke less recursive calls to save time.

The idea is to scan strings from left to right and invoke recursive calls when there is two possible cases (i.e., string a and string b has the same character).
The choice to pass string index instead of copies of substrings greatly saves time. The use of cache to store results of subproblems is key to improve performance. The running time of the given example has decreased from 15s to 0.07s on my laptop when cache is used.

//
//  LeetCode_InterleavingString.cpp
//  Practice
//
//  Created by Junxian Huang on 2/20/13.
//  Copyright (c) 2013 Junxian Huang. All rights reserved.
//

#include <iostream>

using namespace std;

short cache[1000][1000];

class Solution {
public:
    string s1;
    string s2;
    string s3;
    size_t len1;
    size_t len2;
    size_t len3;
    
    bool isInterleave(string _s1, string _s2, string _s3) {
        memset(cache, -1, sizeof cache);
        s1 = _s1;
        s2 = _s2;
        s3 = _s3;
        len1 = s1.length();
        len2 = s2.length();
        len3 = s3.length();
        if (len3 != len1 + len2)
            return false;
        return isInter(0, 0, 0);
    }
    
    bool isInter(int l1, int l2, int l3) {
        if (cache[l1][l2] >= 0) {
            return cache[l1][l2];
        }
        
        while (l3 < len3) {            
            if (l1 == len1) {
                if (s3[l3] == s2[l2]) {
                    l3++;
                    l2++;
                    continue;
                } else {
                    cache[l1][l2] = 0;
                    return false;
                }
            }
            
            if (l2 == len2) {
                if (s3[l3] == s1[l1]) {
                    l3++;
                    l1++;
                    continue;
                } else {
                    cache[l1][l2] = 0;
                    return false;
                }
            }
            
            if (s1[l1] == s2[l2]) {
                if (s1[l1] == s3[l3]) {
                    //special case
                    if (isInter(l1 + 1, l2, l3 + 1)) {
                        cache[l1][l2] = 1;
                        return true;
                    }
                    if (isInter(l1, l2 + 1, l3 + 1)) {
                        cache[l1][l2] = 1;
                        return true;
                    }
                    cache[l1][l2] = 0;
                    return false;
                } else {
                    cache[l1][l2] = 0;
                    return false;
                }
            } else {
                //not equal
                if (s3[l3] == s1[l1]) {
                    l3++;
                    l1++;
                } else if (s3[l3] == s2[l2])  {
                    l3++;
                    l2++;
                } else {
                    cache[l1][l2] = 0;
                    return false;
                }
            }
        }
        cache[l1][l2] = 1;
        return true;
    }
};

/*
int main(int argc, const char *argv[]) {
    Solution s;
    cout << s.isInterleave("bbbbbabbbbabaababaaaabbababbaaabbabbaaabaaaaababbbababbbbbabbbbababbabaabababbbaabababababbbaaababaa", "babaaaabbababbbabbbbaabaabbaabbbbaabaaabaababaaaabaaabbaaabaaaabaabaabbbbbbbbbbbabaaabbababbabbabaab", "babbbabbbaaabbababbbbababaabbabaabaaabbbbabbbaaabbbaaaaabbbbaabbaaabababbaaaaaabababbababaababbababbbababbbbaaaabaabbabbaaaaabbabbaaaabbbaabaaabaababaababbaaabbbbbabbbbaabbabaabbbbabaaabbababbabbabbab"
) << endl;
    
    return 0;
}//*/

leetcode.com/onlinejudge#question_97

bool interleavedStrings(char* str1, char* str2, char* str3)
{
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int len = len1 + len2;
    char* str = new char[len + 1];
    bool result = false;
    interleavedStringsHelper(str1, str2, str, len, str3, result);
    return result;
}

void interleavedStringsHelper(char* str1, char * str2, char* str, int len, char* str3, bool& result)
{
    if (!(*str1) && !(*str2))
    {
        str[0] = NULL;
        if (!strcmp(str3, str - len))
            result = true;
        return;
    }

    if (*str1)
    {
        str[0] = *str1;
        interleavedStringsHelper(str1 + 1, str2, str + 1, len, str3, result);
    }

    if(*str2)
    {
        str[0] = *str2;
        interleavedStringsHelper(str1, str2 + 1, str + 1, len, str3, result);
    }
}

let A and B be two strings and C be interleaved string..
take three pointers each pointing to start of each string.
char * a,b,c;
a->A
b->B
c->C

while(*c!='\0'){
if(*a==*c){a++;}
if(*b==*c){b++;}
c++;
}
if(*a=='\0' && *b=='\0')
{
it is interleaved.
}

sorry..this is incorrect

if both A & B have unique characters i.e. if string A contains a char c then c is not repeated either in A or B, ditto for the chars in B, then add chars of A & B in a hashset and check whether there is a char in C which does not belong to this hashset if not then C is an interleaved string made from A & B. For repeating characters or for the general case hashmap can be used with character being the key and count being the value, add the characters of A & B into the hashmap incrementing their respective count, for chars from C find them in the map and decrement the respective counts, at any stage if there is a char in C which is not in the map or in the end there is any char in map whose count is non zero then C is not interleaved else it is.

Dump the string A and B into map <char, int> where char is key and int is number of occurrence of char ,at the time of dumping the string A and B if duplicate key found increase the int value by 1.
Once dumping is done scan the third string C and check into the map if value field found 0 for any char then its not interleaving or it is.

please give me your feedback.

bool interleavedstring(char * str1, char * str2, char * str3)
{
for (i = 0; i < strlen(str3); i++)
if ( strchr(str1, str3(i)) == null or strchr(str2, str3(i)) == null)
return false; /* the char i in str3 is not found either in str1 nor in str2 hence we can conclude that the string str3 is not interleaved with string str1 and str2*/
return ture: /* the string is interleaved */
}

Keep three pointers, one for each string..Always move pointer of string C..Move pointer of either A or B if they match with element pointed by C..If they do not match return false..That means no interleaving..Move pointer of A or B whichever equal to char pointed by pointer of C..If pointer of C reached its end and pointer of A as well as B should reach its end..if they don't return false..else return true..

Just combine the string and find

if (str1.length() != str2.length())
  {
    return false;
  }

  int charsTracker[26] = {0};

  for (int i = 0; i < str1.length(); i++)
  {
    charsTracker[str1[i] - 'a']--;
    charsTracker[str2[i] - 'a']++;
  }

  for (int i = 0; i < 26; i++)
  {
    if (charsTracker[i] != 0)
      printf("No");
  }

  printf("Yes");
}

Did the interview say an O(n) solution was possible? Or did he just say, can you do better?

function isInterleaved(a, b, c) {
  if(isInterleavedIter(a, b, c, false)) {
    return true;
  }

  return false;
}

function isInterleavedIter(a, b, c, branch) {
  for(var i = 0; i < c.length; i++) {
    if(a[0] == b[0] && !branch) {
      if(isInterleavedIter(b, a, c.slice(i), true)) {
        return true;
      }
    }
    if(c[i] == a[0]) {
      a.shift();
    } else if(c[i] == b[0]) {
      b.shift();
    } else {
      return false;
    }
  }
  return true;
}


isInterleaved('abcd', 'xyz', 'axybczd') => true
isInterleaved('bac', 'acd', 'bacadc') => true

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApp
{

class Program
{



static void Main(string[] args)
{
bool flag = false;
string str1 = Console.ReadLine();
string str2 = Console.ReadLine();
string str3 = Console.ReadLine();
int count = 0;
string final = str1 + str2;
for (int i = 0; i < final.Length; i++)
{
for (int j = 0; j < str3.Length; j++)
{
if (str3[j] == final[i])
{
flag = false;
count++;
break;
}
else
{
flag = true;
}
}

if (flag)
{
Console.WriteLine("sorry no match...");
break;
}

}

if (!flag)
{
Console.WriteLine("matched...");
}













}
}
}

Much simpler Java solution

public static boolean isInterleaved(String str1, String str2, String strI) {
		
		if(str1 == null || str2 == null || strI == null)
			return false;
			
		if(strI.length() != str1.length() + str2.length())
			return false;
		
		if( strI.length() == 0 &&
			str1.length() == 0 &&
			str2.length() == 0)
			return true;
		
		if(str1.length() != 0 && str1.charAt(0) == strI.charAt(0))
			return isInterleaved(str1.substring(1), str2, strI.substring(1));
		else if(str2.length() != 0 && str2.charAt(0) == strI.charAt(0))
			return isInterleaved(str1, str2.substring(1), strI.substring(1));
		else
			return false;
	}

this is very simple code takes only O(n).

import java.util.*;
import java.lang.*;
public class InterleavingCharecter
{
	public static void main (String [] args)
	{
		String input1 = "abc";
		String input2=  "xyz";
		String input3 = "abxcyz";
		int len = input3.length();
		int lenb = input2.length();
		int lena = input1.length();
		//System.out.println(len);
		char a[] = input1.toCharArray();
		char b []= input2.toCharArray();
		char c []= input3.toCharArray();
		System.out.println(c[0]);
		int aa =0  , bb = 0  , cc = 0	;
		for(int i = 0 ;i < len ; i++ )
		{
			if(c[cc] == a [aa])
			{
				System.out.println(c[cc]+":"+a[aa]);
				++cc;
				++aa;
				if(aa >= lena)
				--aa;
			}
			
			else if(c[cc] == b [bb])
			{
				System.out.println(c[cc]+":"+b[bb]);
				++cc;
				++bb;
				if(bb >= lenb)
				--bb;
			}
			else 
			{
			System.out.println("Not Interleaved Correctly");
			System.exit(0) ;

			}
			
		}
		//System.out.println(cc);
		if(cc < len)
		System.out.println("Interleaving is correct but something is miising ");
	
	}

}

def is_interleaved(astr, bstr, cstr):
"""Given three strings, a, b and c, check if c is interleaved from a and b.
For example: a = "abcd", b = "xyz", c = "axbyzcd" => True.
Give a O(n) algorithm"""
ai = bi = 0
for ci in range(len(cstr)):
if ai < len(astr) and cstr[ci] == astr[ai]:
ai += 1
elif bi < len(bstr) and cstr[ci] == bstr[bi]:
bi += 1
else:
return False

return True

First, the interleave preserves relative order of the inputs; this greatly simplifies the problem:

public static boolean isInterleaved(final String A, final String B,
        final String C) {
        if ((A.length() + B.length()) != C.length()) {
            return false;
        }

        int Aiter = 0;
        int Biter = 0;

        for (int Citer = 0; Citer < C.length(); Citer++) {
            if (C.charAt(Citer) == A.charAt(Aiter)) {
                Aiter++;
            } else if (C.charAt(Citer) == B.charAt(Biter)) {
                Biter++;
            }
        }

        if ((Aiter != A.length()) || (Biter != B.length())) {
            return false;
        }

        return true;
    }

//O(n2), handling the case a and b haves common chars.
bool IsInterleave(char* a, char* b, char* c)
{
   if(!*c)
      return !*a && !*b;

   return ((*a == *c) && IsInterleave(a+1, b, c+1)) ||
          ((*b == *c) && IsInterleave(a, b+1, c+1));
}

@jiangok2006 - is ur sol. O(n^2) or O(2^n) ???

public void interleaveStrings(String s1,String s2, String s3){

		HashMap<Character,Integer> map = new HashMap<Character,Integer>();
		int count =0;
		map = populateHashMap(s1,map);
		map = populateHashMap(s2, map);
		
		for(int i =0;i<s3.length();i++){
			if(map!=null && map.containsKey(s3.charAt(i))){
				if(map.get(s3.charAt(i))>1){
					int val = map.get(s3.charAt(i));
					map.put(s3.charAt(i), val-1);
					count++;
				}
				else {
					map.remove(s3.charAt(i));
					count++;
				}	
			}
		}
		if(count==(s1.length()+s2.length())){
			System.out.println("strings are interleaved");
		}
		else{
			System.out.println("strings are not interleaved");
		}
	}
	public HashMap<Character,Integer> populateHashMap(String s,      HashMap<Character,Integer> map){
		
		for(int i = 0;i<s.length();i++){
			if(map.containsKey(s.charAt(i))){
				int value = map.get(s.charAt(i));
				map.put(s.charAt(i), value+1);
			}
			else{
				map.put(s.charAt(i), 1);
			}
		}
		return map;
	}

I think this should run in complexity =O(3n)~ O(n). But then it will i think depend on the length of the string how does this constant factor matters. Please suggest if it does not work for any test string.

Mine sol solves it in O(n)

1) Check the character count(A+B) and C
2) Take first character and last character in 'C' and then check it in one of the smallest string out of A and B.
3) Apply XOR operation to A+B and also apply to C and check the both values are true or false.

use hashmap to store the characters in a and b along with their indices.
use another hashmap to store characters in c and their indices. for each character in c then, just retrieve the values and check whether the index of that character in a or b is lesser then or equal to the index in c. if it is so return true else return false
here is the code

import java.util.HashMap;
import java.util.Map;

public class FindIfStringIsInterleaved {

	public static boolean findIfInterleaved(String a,String b,String c)
	{
		char[] aChar= a.toCharArray();
		char[] bChar= b.toCharArray();
		char[] cChar= c.toCharArray();
		
		Map<Character,Integer> ho= new HashMap<Character,Integer>();
		Map<Character,Integer> hc= new HashMap<Character,Integer>();
		
		boolean isInterleaved= true;
		
		int sumOfInputStrings=a.length()+b.length();
		if(sumOfInputStrings!=c.length())
			return false;
		
		for(int i=0;i<aChar.length;i++)
		{
			ho.put(aChar[i], i);
		}
		for(int i=0;i<bChar.length;i++)
		{
			ho.put(bChar[i], i);
		}
		for(int i=0;i<cChar.length;i++)
		{
			hc.put(cChar[i], i);
		}
		
		for(int i=0;i<cChar.length;i++)
		{
			int vc= hc.get(cChar[i]);
			Object vo= (int)ho.get(cChar[i]);
			if(vo==null)
				return false;
			else if ((int)vo<=vc)
				continue;
			else
				return false;	
		}
		
		return isInterleaved;
	}
	public static void main(String[] args) {
		
		String A="abcd";
		String B="xyz";
		String C="axybczd";
		System.out.println("is the string interleaved? "+findIfInterleaved(A,B,C) );
	}
}

/// public static boolean isInterleaved(String A, String B, String C) {
int a = 0;
int b = 0;
int c = 0;
for(; c < C.length(); c++) {
if(a < A.length() && C.charAt(c) == A.charAt(a)) {
a++;
} else if(b < B.length() && C.charAt(c) == B.charAt(b)){
b++;
}else{
return false;
}
}
return true;
} \\\

public static boolean isInterleaved(String A, String B, String C) {
		if(C.length() != A.length() + B.length()) return false;
		int a = 0;
		int b = 0;
		int c = 0;
		for(; c < C.length(); c++) {
			if(a < A.length() && C.charAt(c) == A.charAt(a)) {
				a++;
			} else if(b < B.length() && C.charAt(c) == B.charAt(b)){
				b++;
			}else{
				return false;
			}
		}
		return true;
	}

bool interleaved(char *a, char *b, char *c)
{
    bool res = false;

    if(*a=='\0' && *b=='\0' && *c=='\0')
        return true;
    if(*a=='\0' && strcmp(b,c)==0)
        return true;
    if(*b=='\0' && strcmp(a,c)==0)
        return true;
    if(strlen(a)+strlen(b) != strlen(c))
        return false;

    while(*c!='\0')
    {
        if(*c==*a)
        {   *a++;
            *c++;
            res = interleaved(a,b,c);
            return res;
        }
        else if(*c==*b) 
        {  
            *b++;
            *c++;
            res = interleaved(a,b,c);
            return res;
        }
        else
        {
            return false;
        }
    }
    
}

boolean isInterleaved(String a, String b, String c)
{
int a_index = 0;
int b_index = 0;

for(int i = 0; i < c.length(); i++)
{
if(a_index < a.length() && a.charAt(a_index) == c.charAt(i))
{
a_index++;
continue;
}

if(b_index < b.length() && b.charAt(b_index) == c.charAt(i))
{
b_index++;
continue;
}

return false;
}

return true;
}

My java solution:
public boolean isInterleaved(String s1, String s2, String s3){
if(s1 == null || s2 == null || s3 ==null){
return false;
}

if((s1+s2).length() != s3.length()){
return false;
}

int j = 1; int k = 0;
String sj = ""; String sk = "";
int len1 = s1.length(0 - 1; int len2 = s2.length() - 1; int len3 = s3.length() - 1;
if((s1.charAt(0) == s3.charAt(0)) && (s1.charAt(len1) == s3.charAt(len3))){
sk = s2; sj = s1;
} else if((s2.charAt(0) == s3.charAt(0)) && (s2.charAt(len1) == s3.charAt(len3))){
sk = s1; sj = s2;
} else { return false; }

for(int i = 1; i < len3 -1; i++){
if(sk.charAt(k) == s3.charAt(i)){
k++;
} else if(sj.charAt(j) == s3.charAt(i)) {
j++;
} else { return false; }
}
return true;
}

Solution in Python. This uses recursive backtracking to handle the cases where there are local matches from str1 and str2, and we don't know which one to use before-hand. It it not O(n). Are there any solutions in these comments that are linear (and really work)?

def is_interweaved(s1, s2, s3, positions=(0,0,0)):
    (i1,i2,i3) = positions
    if len(s1)+len(s2) != len(s3): return False
    if i3==len(s3): return True
    
    s1_match = i1<len(s1) and s1[i1]==s3[i3]
    s2_match = i2<len(s2) and s2[i2]==s3[i3]
    
    # cases with no branching into multiple scenarios
    if s1_match and not s2_match:
        return is_interweaved(s1,s2,s3,(i1+1,i2,i3+1))
    if s2_match and not s1_match:
        return is_interweaved(s1,s2,s3,(i1,i2+1,i3+1))
    if not s1_match and not s2_match:
        return False
        
    # case where both strings match, so we do branch
    if s1_match and s2_match:
        result = is_interweaved(s1,s2,s3,(i1+1,i2,i3+1))
        if result: return True
        result = is_interweaved(s1,s2,s3,(i1,i2+1,i3+1))
        if result: return True
        return False

simple O(n) algo. passes all test cases.
algo:
1) traverse the COMBO once for each string(A and B)
2) if the char is in A make it null and move on the next char of A.
3)repeat for this for string B.
4) check if COMBO has been converted to null.

code:(in c++)

bool isInterleaved(string a, string b, string comb){

    if(a.length()+b.length()!= comb.length()) return false;
       int j(0);
    for(int i(0); i<comb.length(); i++){
        if (j==a.length() ) break;
        if(comb[i]==a[j]) {comb[i] = '\0';j++;}
    }
    j=0;
    for(int i(0); i<comb.length(); i++){
        if (j==b.length() ) break;
        if(comb[i]==b[j]) {comb[i] = '\0';j++;}
    }
    for(int i(0); i<comb.length(); i++){
        if(comb[i]!= '\0') return false;
    }
    return true;
}

I think we can solve this problem following three steps:
First : check Histogram for a+b and c is the same O(N);
Second: remove duplicate character from a,b,and c. E.G. "AAA" after remove duplicate "A" O(N)
Third: check a and b is orderly contained in c O(N)

boolean HaveSameHistogram(String aa,String bb)
	{
		char[] a = aa.toCharArray();
		char[] b = bb.toCharArray();
		int ad[] = new int[26];
		int bd[] = new int[26];
		int alen = a.length;
		int blen = b.length;
		for(int i=0;i<alen;i++)
		{
			ad[a[i]-'a'] ++;
		}
		for(int i=0;i<blen;i++)
		{
			bd[b[i]-'a'] ++;
		}
		for(int i=0;i<26;i++)
		{
			if(ad[i]!=bd[i]) return false;
		}
		return true;
	}
String removeDuplicate(String src)
	{
		int his[] = new int[26];
		char [] r = src.toCharArray();
		String s = "";
		for(int i=0;i<r.length;i++)
		{
			if(his[r[i]-'a']==0){s+=r[i];his[r[i]-'a']++;};
		}
		
		return s;
	}
boolean IsOrderlyContained(String parent,String child)
	{
		char[] pp = parent.toCharArray();
		char[] cc = child.toCharArray();
		int pi=0,ci=0;
		while(ci<cc.length)
		{
			if(pp[pi]==cc[ci]){pi++;ci++;if(pi>=pp.length) return false;}
			else {pi++;if(pi>=pp.length) return false;}
		}
		return true;
	}
boolean string_interleaved(String a,String b,String c)
	{
		if(!HaveSameHistogram(a+b,c)) return false;
		String aa = removeDuplicate(a);
		String bb = removeDuplicate(b);
		String cc = removeDuplicate(c);
		if(IsOrderlyContained(cc,aa) && IsOrderlyContained(cc,bb)) return true;
		return false;
	}

public class StringInterleave {
    public boolean isInterLeave(String a, String b, String target) {
        int aIndex = 0;
        int aSize = a.length();
        
        int bIndex = 0;
        int bSize = b.length();
        
        for (int i = 0; i < target.length(); ++i) {
            char targetChar = target.charAt(i);
            if (aIndex < aSize && a.charAt(aIndex) == targetChar) {
                ++aIndex;
            } else if (bIndex < bSize && b.charAt(bIndex) == targetChar) {
                ++bIndex;
            }
        }
        return aIndex == aSize && bIndex == bSize;
    }
    
    public static void main(String[] args) {
    	String A="abcd", B="xyz", C="axybczd";
        System.out.println(new StringInterleave().isInterLeave(A, B, C));
	}
}

#include<stdio.h>
#include<string.h>
int interl(char *A,char *B,char *C)
{
int l1 = strlen(A);
int l2 = strlen(B);
int l3 = strlen(C);
if(l3 != (l1+l2))
return 0;
while(*C != '\0')
{
if(*A != '\0' && *A == *C)
A++;
else if(*B != '\0' && *B == *C)
B++;
else
return 0;
C++;
}
return 1;
}
int main()
{
while(1){
char A[10],B[10],C[20];
scanf("%s%s%s",&A,&B,&C);
interl(A,B,C)>0?printf("YES"):printf("NO");}

}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct queue{
    struct node *head;
    struct node *tail;
};

struct node{
    char data;
    struct node *next;
};
struct queue *init_queue() {
    struct queue* q = (struct queue*)malloc(sizeof(struct queue));
    if(!q)
        return NULL;
    
    q->head = NULL;
    q->tail = NULL;
    return q;
}

int enqueue(struct queue* q, char data) {
     struct node *n = (struct node*)malloc(sizeof(struct node));
     if(!n)
         return -1;
     n->data = data;
     n->next = NULL;
     
     if(q->tail) {
         q->tail->next = n;
         q->tail = n;
     } else {
         q->head = n;
         q->tail = n;
     }
     return 0;
}

char dequeue(struct queue *q) {
	char data = '\0';
    if(q->head) {
        struct node* tmp = q->head;
        q->head = q->head->next;
        if (q->head == NULL) {
            q->tail = NULL;
        }
        
        data = tmp->data;
        free(tmp);
        return data;
    } else
        return '\0';
}

// peek the value in head
char peek_queue(struct queue *q) {
    if (q->head)
        return q->head->data;

    return '\0';
}

// return 0 if success
int check_interleave(struct queue *q, char *a, char *b, char *c) {
    int lena = strlen(a);
    int lenb = strlen(b);
    int lenc = strlen(c);
    int indexa = 0;
    int indexb = 0;
    int indexc = 0;
    
    if ((lena + lenb) != lenc)
        return -1;
        
    while(c[indexc]) {
        char c_inqueue = peek_queue(q);
        if(c_inqueue && c_inqueue == c[indexc]) {
            indexc++;
            dequeue(q);
            continue;
        }
        if (a[indexa] != b[indexb]) {
            if(a[indexa] == c[indexc]) {
                indexa++;
                indexc++;
                continue;
            } else if(b[indexb] == c[indexc]) {
                indexb++;
                indexc++;
                continue;
            } else
                return -1;
        } else if(a[indexa] == b[indexb] && a[indexa] == c[indexc]) { // confict! put current char into queue
            enqueue(q, a[indexa]);
            indexa++;
            indexb++;
            indexc++;
        } else
            return -1;
    }
    if (peek_queue(q))
        return -1;
        
    return 0;
}

int main() {
    char a[5] = {'a', 'c', 'd', 'f', '\0'};
    char b[4] = {'c', 'y', 'z', '\0'};
    char c[8] = {'a', 'c', 'y', 'c', 'd', 'f', 'z', '\0'};
    
    int ret = check_interleave(init_queue(), a, b, c);
	printf("ret: %d\n", ret);
	return 0;
}

The following solution uses space l*m*n where l, m, n are respectively the lengths of the string A, B and C. It is a memoization based solution to the simplest recursive solution to the problem. The memoization leads to increased memory usage but keeps the run time polynomial.

Recursive algo :
Let i,j,k be running pointers to the strings A, B and C respectively. Basically what the code does is try to match the character at the pointer location in C to the characters at the pointer locations in A and B. If a match is found then the respective pointers are moved forward.

boolean check_interleave(i, j, k){
    /* If we have a mismatch in the number of C characters remaining and those in A and B*/
    /* then an interleaving is impossible */
    if(n-k != l-i + j-k)
        return false;
    /*  Can we match the current C character with A ? */
    if((a[i] == c[k]) && check_interleave(i+1,j,k+1))
        return true;
    /* Can we match the current C character with B ? */
    if((b[j] == c[k]) && check_interleave(i,j+1,k+1))
        return true;
    /* If we cannot match the current C character then no interleaving is possible */
    if((a[i] != c[k]) && (b[j] != c[k]))
        return 0;

Invoking check_interleave(1,1,1) will give us the result.

For sake of clarity I have not checked for boundary conditions when we reach the end of a string.
Now this code runs in worst case exponential time since it will check all possible interleavings.
The way out of this is to maintain an array RES[l][m][n] which contain the results of the
intermediate computations of check_interleave(.,.,.).

To use this array we initialize all its entries to some junk value say -1. Now when check_interleave
is called at some location, say check_interleave(2,5,6), the code checks if RES[2][5][6] is set or not.
If it is set to true/false then we simply use that result. If not then we compute the result and apart
from using it, also store it in RES at the appropriate location.

The total runtime of this procedure is O(lmn) : since the procedure has been described in a top down
fashion it might not be clear that the runtime is indeed polynomial. However a simple conversion
of this routine to a dynamic programming solution will convince one of the runtime bounds.

def isInterleaved(a,b,c):
    if c=="":
        return True
    output=False
    if len(a)>0 and a[0]==c[0]:
        output|=isInterleaved(a[1:], b, c[1:])
    if len(b)>0 and b[0]==c[0]:
        output|=isInterleaved(a, b[1:], c[1:])
    return output

// CheckInterleavedStrings.cpp
//

#include <iostream>

using namespace std;

bool checkInterleaved(string str1, string str2, string str3)
{
	if (str1.length() == 0 || str2.length() == 0)
		return false;

	if(str3.length() != (str1.length() + str2.length()))
		return false;

	int i = 0;
	int str1Index = 0;
	int str2Index = 0;
	
	for(;i<str3.length();i++)
	{
		if(str3[i] == str1[str1Index])
			str1Index++;
		else if(str3[i] == str2[str2Index])
			str2Index++;
		else
		{
			cout << "NOT INTERLEAVED" << endl;
                        return false;

		}
	}

	if(str1Index != str1.length() || str2Index != str2.length())
	{
  	    cout <<  "NOT INTERLEAVED" << endl;
            return false;
        }
	else
        {
		cout << "INTERLEAVED" << endl;
         
	}
       return true;
}

//interleaved strings
// recursive approach
//code is self explanatory 

#define SIZE 50

int isInterleaved(char* stringA,char* stringB,char* stringC, int pA, int pB, int pC)
{
    
    if( (stringA[pA]=='\0') && (stringB[pB]=='\0') && (stringC[pC]=='\0') )
    {
        return 1;
    }
    if( (stringA[pA]!=stringC[pC]) && (stringB[pB]!=stringC[pC]) )
    {
        return 0;
    }
    if(stringA[pA]==stringC[pC])
    {
       return isInterleaved(stringA,stringB,stringC,pA+1,pB,pC+1);
    }
    if(stringB[pB]==stringC[pC])
    {
       return isInterleaved(stringA,stringB,stringC,pA,pB+1,pC+1);
    }
    
    return 0;
    
}

int CheckInterleaved(char * stringA,char *stringB,char *stringC)
{
    int lA = strlen(stringA);
    int lB = strlen(stringB);
    int lC = strlen(stringC);
    if(lC!=(lA+lB)) return 0;
    else 
    return isInterleaved(stringA,stringB,stringC,0,0,0);
} 

int main()
{
    char stringA[SIZE] ={'\0'};
    char stringB[SIZE] ={'\0'};
    char stringC[SIZE+SIZE] = {'\0'};
    scanf("%s%s%s",stringA,stringB,stringC);
    if(!!CheckInterleaved(stringA,stringB,stringC))
    {
        printf("YES YES YES !!!\n");
    }
    else
    {
        printf("NO NO NO !!!\n");
    }
    
}

How come this was so complicated? Did I miss sth?

bool interleaved (const std::string & A, const std::string & B, const std::string & C)
{
    if (A.size () + B.size () != C.size ())
    {
        return false;
    }

    int a (0);
    int b (0);
    for (int c = 0; c < C.size (); ++c)
    {
        if (a < A.size () && C.at (c) == A.at (a))
        {
            ++a;
        }
        else if (b < B.size () && C.at (c) == B.at (b))
        {
            ++b;
        }
        else
        {
            break;
        }
    }
    return false;
}

Aggregate XOR of each character of a,b and c.

bool isInterleaved(string a,string b,string c) {
    
    int xor_result=0;
    
    if(a.length() +b.length() != c.length())
        return false;
    
    for(int i=0;i<a.length();i++)
        xor_result = xor_result ^ a.at(i);

    for(int i=0;i<b.length();i++)
        xor_result = xor_result ^ b.at(i);
    
    for(int i=0;i<c.length();i++)
        xor_result = xor_result ^ c.at(i);
    
    
    if(xor_result == 0) // interleaved
        return true;
    else
        return false;
    
}

Be simple ! using a temporary string

bool is_interleaved(string A, string B, string C){
  int a=0, b=0, t=0;

  string T;
  for(int c=0; c < C.size(); ++c){
    if (a < A.size() && C[c] == A[a]){
      ++a;
      if(b < B.size() && C[c] == B[b]){
        T += B[b++];
      }
    }
    else if(b < B.size() && C[c] == B[b]) ++b;
    else if(t < T.size() && C[c] == T[t]) ++t;
    else
      return false;
  }

  return true;
}

public bool checkInterleave(string a, string b, string c)
        {
            if (a.Length + b.Length != c.Length)
                return false;
            int cA = 0, cB = 0, cC = 0;
            while (cC < c.Length)
            {
                if (cA<a.Length && cB<b.Length && a[cA] == b[cB])
                    return checkInterleave(a.Substring(cA + 1, a.Length - cA - 1), b.Substring(cB, b.Length - cB), c.Substring(cC + 1, c.Length - cC - 1)) || checkInterleave(a.Substring(cA, a.Length - cA), b.Substring(cB + 1, b.Length - cB - 1), c.Substring(cC + 1, c.Length - cC - 1));
                else if (cA < a.Length && a[cA] == c[cC])
                {
                    cA++;
                }
                else if (cB < b.Length && (b[cB] == c[cC]))
                {
                    cB++;
                }
                else return false;
                cC++;
            }
            if (cA == a.Length && cB == b.Length && cC == c.Length)
                return true;
            else return false;

}

private boolean testStringInterleaved(){
		
		String A = "abcd";
		String B = "xyz";
		String C = "axybczd";
		
		char Achar[] = A.toCharArray();
		char Bchar[] = B.toCharArray();
		char Cchar[] = C.toCharArray();

		int i, j, k;

		if(C.length() == (A+B).length()) {
			for(i=0, j=0, k=0;  k < Cchar.length ; k++) {
	
			if (i<Achar.length && Achar[i] == Cchar[k])
				i++;
			else if (j < Bchar.length  && Bchar[j] == Cchar[k])
				j++;
			else
				return false;
			}
		}else{
			
			return false;
		}
		return true;
	}

My DP solution:

boolean check(String A, String B, String C) {

    if (A.length() + B.length() != C.length()) {
        return false;
    }

    boolean[][] marked = new boolean[A.length() + 1][B.length() + 1];

    marked[0][0] = true;

    for (int i = 0; i <= A.length(); i++) {
        for (int j = 0; j <= B.length(); j++) {


            if (i > 0 && A.charAt(i - 1) == C.charAt(i + j - 1)) {
                marked[i][j] |= marked[i - 1][j];
            }

            if (j > 0 && B.charAt(j - 1) == C.charAt(i + j - 1)) {
                marked[i][j] |= marked[i][j - 1];
            }


        }
    }

    return marked[A.length()][B.length()];
}

int main()
{
	string s1,s2,s3;
	int i,n,m,p,j,k;
	cin>>s1>>s2>>s3;
	n=s1.size();
	m = s2.size();
	p = s3.size();
	if (p != m+n){cout<<"No\n";return 0;}
	i = 0;j=0;k=0;
	while(i<p && j<p)
	{
		if(i<n && s1[i] == s3[k]){i++;k++;continue;}
		if(j<m && s2[j] == s3[k]){j++;k++;continue;}
		break;
	}
	if (i==n && j==m && k==p){cout<<"Yes\n";return 0;}
	cout<<"No\n";
	return 0;

}

Combine both the strings (A+B) and sort it. Then sort string C. If both are equal, then yes else no.

bool string_interleaved(char *str1,char *str2,char *c)
{
    int count1[256]={0};
    int count2[256]={0};
//find length of each string
    int len1=strlen(str1),len2=strlen(str2),len3=strlen(c),p=0;
    int i;
//if lengths are unequal
        if((len1+len2)!=len3)
            return false;

             for(i=0;i<(len1+len2)&&i<len3;i++)
                    {
				if(i<len1)
					count1[str1[i]]++;
				else
				  {
					count1[str2[p]]++;
					p++;
				  }
			count2[c[i]]++;
		     }

				for(i=0;i<256;i++)
				if(count1[i]!=count2[i])
				return false;
         return true;
}

bool string_interleaved(char *str1,char *str2,char *c)
{
    int count1[256]={0};
    int count2[256]={0};
//find length of each string
    int len1=strlen(str1),len2=strlen(str2),len3=strlen(c),p=0;
    int i;
//if lengths are unequal
        if((len1+len2)!=len3)
            return false;

             for(i=0;i<(len1+len2)&&i<len3;i++)
                    {
				if(i<len1)
					count1[str1[i]]++;
				else
				  {
					count1[str2[p]]++;
					p++;
				  }
			count2[c[i]]++;
		     }

				for(i=0;i<256;i++)
				if(count1[i]!=count2[i])
				return false;
         return true;
}

Solution:

The codes mentioned above will not work in case of common characters in both the strings.

When common characters are found, we shuld move with one possibility. The other possibility is stored on Stack, with the help of three index where we would resume.

When we are stuck finding no interleaving, we would pop the vales from stack, and resume.

When the stack is empty, and still we don't find interleaving, we declare "No interleaving."
Hope this helps.

I think the algorithm can be laid out as follows,

1. First check the length of the concatenation of the first and second string and the length of the third string is equal. if not return false.

2. Then check if all the characters in the concatenation is present in the third string.
if all the characters are not present return false.

3. Check if the third string begins with either the first or the second string. If it does with either then the first and the second string is not interleaved.

Three simple checks all of O(n) time complexity.

A very simple java code that takes O(N) and uses set

package practicepackage;

import java.util.TreeSet;
import java.util.Set;

public class FindIfStringIsInterleaved {

	public static boolean findIfInterleaved(String a,String b,String c)
	{
		if ((a+b).length()!=c.length())
			return false;
		char[] sum= (a+b).toCharArray();
		char[] cChar= c.toCharArray();
		Set<Character> input= new TreeSet<Character>();
		for(int i=0;i<sum.length;i++)
			input.add(sum[i]);
		for(int j=0;j<sum.length;j++)
			input.remove(cChar[j]);
		if(input.isEmpty())
			return true;
		else
			return false;
	}
	public static void main(String[] args) {
		
		String A="abcd";
		String B="xyz";
		String C="axybczd";
		System.out.println("is the string interleaved? "+findIfInterleaved(A,B,C) );
	}
}

Here is what I think:
1) First check length of A+B = C if true then
2) Decide which string A or B has First character in C, Both A and B are same then continue traversing C until we find Unique element. Hence we can find which string is the first one.
3) Now we know that string interleaving is starting from first string so we can continue scanning second and then first by taking turn.

How about taking two hash tables (one for together string1 and string2, and another for string3) of 26 size and incrementing the size of key when ever a char is found and then comparing both the tables if they have equal keys and values by using hashtable1.toString() == hashtable2.toString()

I am not sure about this. Just a different approach

Hi i made this code in c and its working u can check it

#include<stdio.h>
#include<string.h>
int main()
{
char a[]="xyz";
char b[]="abc";
char c[]="axytbc" ;
check(a,b,c);

getch();
return 0;

}
int check(char *a,char *b, char *c)
{
int i=0,flag=1;
while(i<strlen(c))
{
if(*c==*a || *c==*b)
{
if(*c==*a)
{*c++;
*a++;}
else
{*c++;
*b++;}
i++;
}
else{
printf("NO");
flag=0;
break;

}
}
if(flag==1)
printf("yes");

}

bool isInterleaved(char* s1, char* s2, char *s3)
{
  if(strlen(s3) != strlen(s2)+strlen(s1))
  return false;

  if(s3 == null)
    return s1==null && s2==null;
  
  while(*s3 != '\0')
  {
    if(*s3++==*s1) s1++;
    else if(*s3++==*s2) s2++;
    else break;
  }

  return *s3 == '\0';
}

This solution is O(n). The logic is start tracing two string consequently until the end.

bool interleaveTest(char *a, char *b, char *c)
{
	int seta=0, setb=0;
	while(*c!='\0')
	{
		if(*c!=*a && *c!=*b) {
			if(*c==*(a-seta)) {
				a-=seta;
				seta=setb=0;
			}
			else if(*c==*(b-setb)) {
				b-=setb;
				seta=setb=0;
			}
			else
				return false;
		}
		if(*c==*a) {
			seta++;
			a++;
		}
		else {
			a-=seta;
			setb=seta=0;
		}
		if(*c==*b) {
			setb++;
			b++;
		}
		else {
			b-=setb;
			seta=setb=0;
		}
		c++;
	}
	return true;
}