Country: United States

Comment hidden because of low score. Click to expand.
6
of 6 vote

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.

Comment hidden because of low score. Click to expand.
0

``````private static boolean isInterleaved(char ac[],char bc[], char ic[]) {
System.out.println("compare = " +new String(ac) + "+" +
new String(bc) + "=" + new String(ic));

int ap= 0;
int bp = 0;
int counter = 0;

if (ac.length + bc.length != ic.length)
return false;

for (int i = 0; i < ic.length; i++) {
char a1 = ap >= ac.length ? '\0' : ac[ap];
char b1 = bp >= bc.length ? '\0' : bc[bp];

if (a1 == ic[i] && b1 == ic[i]) {
counter++;
ap++;
bp++;
continue;
}
if (a1 == ic[i]) {
ap++;
bp-=counter;
counter = 0;
continue;
}
if (b1 == ic[i]) {
bp ++;
ap -=counter;
counter = 0;
continue;

}
if (counter > 0) {
if (ac[ap-counter] == ic[i]) {
counter--;
continue;
}
}
return false;
}
return true;
}``````

Comment hidden because of low score. Click to expand.
0

there is a online judge for this question on leetcode, your code fails

Comment hidden because of low score. Click to expand.
3
of 3 vote

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.
//

#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;
}//*/``````

Comment hidden because of low score. Click to expand.
0

Here is a much simpler version of your code which got AC on leetcode in 28 ms.

``````class Solution
{
public:
short dp[1000][1000];
string s1,s2,s3;
int len1,len2,len3;
bool fun(int l1, int l2)
{
int l3=l1+l2;
if(l3==len3)
return true;
if (dp[l1][l2] >= 0)
return dp[l1][l2];
bool x=0;
if(l2<len2 && s3[l3] == s2[l2])
x=fun(l1,l2+1);
if (!x && l1<len1 && s3[l3] == s1[l1])
x=fun(l1+1,l2);
return dp[l1][l2] = x;
}
bool isInterleave(string _s1, string _s2, string _s3)
{
memset(dp, -1, sizeof dp);
s1 = _s1;
s2 = _s2;
s3 = _s3;
len1 = s1.length();
len2 = s2.length();
len3 = s3.length();
if (len3 != len1 + len2)
return false;
return fun(0, 0);
}
};``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

leetcode.com/onlinejudge#question_97

Comment hidden because of low score. Click to expand.
0
of 4 vote

``````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);
}
}``````

Comment hidden because of low score. Click to expand.
0

This seems correct and follows the approach of generating the interleavings. But it might end up generating all the interleavings before returning the final result.

Comment hidden because of low score. Click to expand.
0

In that case we can add this code snippet in the beginning of
definition of interleavedStrings function

``````if (result)
return;``````

Comment hidden because of low score. Click to expand.
0

Does this run on O(n)?

Comment hidden because of low score. Click to expand.
0

@pranaymahajan
even with this condition how would it save the worst case of generating all interleavings. Lets say the final interleaving would be the deciding factor for true or false for the given questions. still we would land back to square one.

what say?

Comment hidden because of low score. Click to expand.
0

@mr i think you are right

Comment hidden because of low score. Click to expand.
0

pretty simple use an array of 26 length initialize it to zero u can use 257 length also but it depends the type of character set you are using read string a "+1" for every character similarly for every character in b.Now start reading string c do "-1" for every character on array if at any time the value in array goes below 0 while doing -1 then it is not interleaved,after doing this do check whether whole array is agail zero or not if not again not interleaved.
actualyy this problem is that finding whether c is a permutation of string "a+b".

Comment hidden because of low score. Click to expand.
0

for interleaving order must be same.

One thing I want to ask interleave means the strlen(str3) = strlen(str2) + strlen(str1) with order maintained?? If any other letter is present that is present none of str1 and str2 will not be considered as interleave right?

Comment hidden because of low score. Click to expand.
0

``````#include<stdio.h>

// Returns true if C is an interleaving of A and B, otherwise
// returns false
bool isInterleaved (char *A, char *B, char *C) {
bool ans = false ;
// Iterate through all characters of C.
while (*C != 0) {
// Search For Both
if ( (*A == *B) && (*A == *C) ) {
//printf ( "\nMatches %c Remaining a =%s, b=%s\n", *A,A,B) ;
ans = isInterleaved (A+1, B, C+1) ;
ans = ans || isInterleaved (A, B+1, C+1) ;
return ans ;
}
// Match first character of C with first character of A,
// If matches them move A to next
if (*A == *C)
A++;

// Else Match first character of C with first character of B,
// If matches them move B to next
else if (*B == *C)
B++;

// If doesn't match with either A or B, then return false
else
return false;

// Move C to next for next iteration
C++;
}

// If A or B still have some characters, then length of C is smaller
// than sum of lengths of A and B, so return false
if (*A || *B)
return false;

return true;
}

// Driver program to test above functions
int main() {
char A[] = "ABBC";
char B[] = "ABD";
char C[] = "AABBDBC";
if (isInterleaved(A, B, C) == true)
printf("%s is interleaved of %s and %s", C, A, B);
else
printf("%s is not interleaved of %s and %s", C, A, B);

return 0;
}``````

Comment hidden because of low score. Click to expand.
0

The solution is right, but I don't think it's O(n) solution, since the algorithm generates all possible interleaved results.

Comment hidden because of low score. Click to expand.
0

Yep. By constructing every possible interleaving the complexity is exponential.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.
}

Comment hidden because of low score. Click to expand.
0

we need more checks since a and b both might contain few common characters in them which would dismangle the parameters and return false even when it should return true.

e.g. A -> bac
B -> acd

Comment hidden because of low score. Click to expand.
0

I think, else should be there after if statement to prevent the above condition mentioned by _mr.

Comment hidden because of low score. Click to expand.
0

You can make a slight variation to solve the issue `mr` stated.

``````#include <iostream>

int main()
{
const char* s1 = "bac";
const char* s2 = "acd";

const char* n = s1;
const char* m = s2;
const char* p = s3;

while (*p && (*n || *m)) {

if (*m && *p == *m) {
m++;
p++;
}

if (*n && *p == *n) {
n++;
p++;
}
}

if (!(*p || *m || *n)) {
std::cout << "Interleaved" << std::endl;
}``````

Comment hidden because of low score. Click to expand.
0

pl help me to understand..if(*n && *p==*n) condition...what is the meaning of this condition 'if( *n'....what it is being evaluated to...
and if(!(*p || *m || *n))...what are we checking here? how the condition is evaluated here.

Comment hidden because of low score. Click to expand.
0
of 0 vote

sorry..this is incorrect

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

I don't think you considered the fact that the order of A,B should be preserved in C

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 */
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 4 vote

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");
}``````

Comment hidden because of low score. Click to expand.
0

Interleaving could start from Either string A or string B so before scanning C, we need to decide which string will go first out of A and B.

Comment hidden because of low score. Click to expand.
0

you didn't understand my solution it say that first I combine both A and B and make string 1 and then I am comparing with C ie string2...

Comment hidden because of low score. Click to expand.
0

Interleaved means the relative ordering of characters in the strings must be the same. This solution just checks whether all characters are present in the right numbers

Comment hidden because of low score. Click to expand.
0

in charsTracker[str1[i] - 'a']-- , what will happen in brackets [str1[i]-'a']....i.e why r we doing like this

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 2 vote

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

Comment hidden because of low score. Click to expand.
0

This solution passes ('abc' , 'abc' ,'aabbcc')
but your second example should fail (result is 6 chars input total 7 chars)
The solution also passes ('abc', 'abbc', 'ababcbc')

not sure it is O(n) though..

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

namespace ConsoleApp
{

class Program
{

static void Main(string[] args)
{
bool flag = false;
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...");
}

}
}
}

Comment hidden because of low score. Click to expand.
0
of 4 vote

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

Comment hidden because of low score. Click to expand.
0

It looks correct.
Remove recursion and try to do it using iterations. Then space complexity will reduce to o(1)

Comment hidden because of low score. Click to expand.
0

I don't think this works.

This algorithm always takes chars from str1 if it looks like a match. But this can get us into trouble.

Suppose str1 is 'abx' and str2 is 'aby'. Suppose the third string is 'abyabx'. This should return True, but since your algorithm begins by feeding off of str1 instead of str2, it will return False.

Am I missing something?

(I have a proposed solution in the comments that uses recursive backtracking to handle the case of both strings locally matching.)

Comment hidden because of low score. Click to expand.
0
of 4 vote

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

}``````

}

Comment hidden because of low score. Click to expand.
0

This's is incorrect. how about A='aaa' B='ab' and C='abaaa' ? Ur solution would give false, which is clearly not the case

Comment hidden because of low score. Click to expand.
0

Think this should work...have tried it on a few test cases and looks OK so far.

``````bool isInterLeaved(string str1, string str2, string str3, int& l1, int& l2, string& work, int index)
{
if (work.compare(str3) && l1 == str1.size() && l2 == str2.size())
{
return false;
}
if (!work.compare(str3) && l1 == str1.size() && l2 == str2.size())
{
return true;
}

for (int i = index; i<str3.length() ; i++)
{
if (str1[l1] == str3[i] && str2[l2] == str3[i])
{
work += str1[l1];
l1 +=1;
if(isInterLeaved(str1,str2,str3,l1,l2,work,index+1)) return true;
else
{
l1 -= 1;
l2+=1;
if (isInterLeaved(str1,str2,str3,l1,l2,work,index+1)) return true;
else
{
return false;
}
}
}
else if (str1[l1] == str3[i])
{
work += str1[l1];
l1 += 1;
index++;
}
else if (str2[l2] == str3[i])
{
work += str2[l2];
l2 += 1;
index++;
}
else
{
return false;
}
}

if (!work.compare(str3) && l1 == str1.size() && l2 == str2.size())
{
return true;
}

return false;
}

int main(int argc, char *argv[])
{
string str1("aaa");
string str2("ab");
string str3("aaaab");

string working;
int index =0;
int li = 0,ri=0;
bool ans = isInterLeaved(str1,str2,str3,li,ri,working,index);
cout<<ans<<endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//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));
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 4 vote

``````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.

Comment hidden because of low score. Click to expand.
0

Why to create 2 maps just combine S1 and S2 and create a single map but first of check length of S1+S2 and S3 are same

Comment hidden because of low score. Click to expand.
0

Order is also an important part in this question. It will unable to detect the order.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Mine sol solves it in O(n)

Comment hidden because of low score. Click to expand.
0
of 2 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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) );
}
}``````

Comment hidden because of low score. Click to expand.
0

It will take O(N)

Comment hidden because of low score. Click to expand.
0

Consider the strings are:
ab, ab, abba

The indices are:
a - 0, b - 1; a - 0, b - 1; a - 0,4, b - 1,2

Based on your logic, this comes out to be true, which it is not.

Comment hidden because of low score. Click to expand.
0
of 0 vote

/// 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;
} \\\

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

does not work if A and B have few common characters

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 bd[] = new int[26];
int alen = a.length;
int blen = b.length;
for(int i=0;i<alen;i++)
{
}
for(int i=0;i<blen;i++)
{
bd[b[i]-'a'] ++;
}
for(int i=0;i<26;i++)
{
}
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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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");}

}

Comment hidden because of low score. Click to expand.
0
of 6 vote

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

struct queue{
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->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->tail = n;
}
return 0;
}

char dequeue(struct queue *q) {
char data = '\0';
q->tail = NULL;
}

data = tmp->data;
free(tmp);
return data;
} else
return '\0';
}

// peek the value in head
char peek_queue(struct queue *q) {

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

Comment hidden because of low score. Click to expand.
0

put the conflict one into a queue

Comment hidden because of low score. Click to expand.
0

yeah.......ur right

Comment hidden because of low score. Click to expand.
0

given string a, b and s, start from the beginning of them, if no conflict, shift. conflict: a[i] == b[j] == s[k], put this char into queue and continue.note: match the char in queue with s first

Comment hidden because of low score. Click to expand.
0

A = abc
B = amn
C = amnbca
should be false, but your algo returns true...

Comment hidden because of low score. Click to expand.
0

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

// return 0 if success
int match(char *s1, char *s2, char *s3) {
if(!s3)
return 0;

if (s1[0] && s2[0]) {
if (s1[0] != s2[0]){
if (s1[0] != s3[0] && s2[0] != s3[0]) {
return 1;
} else if (s1[0] == s3[0]) {
return match(&s1[1], s2, &s3[1]);
} else
return match(s1, &s2[1], &s3[1]);
} else {
return match(s1, &s2[1], &s3[1]) & match(&s1[1], s2, &s3[1]);
}
} else if (!s1[0]) {
if (!strcmp(s2, s3))
return 0;
return 1;
} else {
if (!strcmp(s1, s3))
return 0;
return 1;
}
}

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

a recursive method, not O(n) if conflict exists

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 2 vote

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

Comment hidden because of low score. Click to expand.
0

right approach but returns true for 'a','b','a'

here's how i wrote it:

``````def interl(A,B,C):
if not any((A,B,C)):
return True
if not C:
return
c = C[0]
solutions = []
print A,B,C
if A and A[0] == c:
solutions.append(interl(A[1:], B, C[1:]))
if B and B[0] == c:
solutions.append(interl(A, B[1:], C[1:]))
return any(solutions)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// 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;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````//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");
}

}``````

Comment hidden because of low score. Click to expand.
0

``````//if strings have duplicates
// start both the calls, one should return 1
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]) && (stringB[pB]==stringC[pC]) )
{
return isInterleaved(stringA,stringB,stringC,pA+1,pB,pC+1)||isInterleaved(stringA,stringB,stringC,pA,pB+1,pC+1);
}
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;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

Sorry mistyped ... it should have been:
break => return false;
the last "return false" => "return true;"

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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()];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

sorting will take O(nlogn) time...question has asked for O(n) algo

Comment hidden because of low score. Click to expand.
0

sorting will change the relative order of the elements which is preserved in case of interleaving the 2 strings.

we just need to check
1) 2 strings are of equal length
2) the elements of str1 and str2 are in the same order in str3

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

The application of the above 3 steps is not enough to check the interleaving of two string. Consider the following example-
str1 = "acb", str2 = "def", str3 = "abcdef"

Although the above string combinations satisfies all the three conditions mentioned above, still, str3 is not the interleaved string combination for str1 and str2

Comment hidden because of low score. Click to expand.
0

What is the other conditions we need to apply here. what does interleaved mean?

Can you provide me some other sample inputs and outputs?

Comment hidden because of low score. Click to expand.
0

@pranaymahajan

You are right, I overlooked it. After thinking a while it seems a good idea to confirm if the two strings are distinct, which they should be.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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++)
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) );
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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()

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````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';
}``````

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

tried this but it was incorrect
output was:

('abcd', 'xyz', 'axybczd') => false
('abc' , 'abc' ,'aabbcc') => true
('abc', 'abbc', 'ababcc') => false

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.