Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

You are given three strings: a, b and i. Write a function that checks whether i is an interleaving of a and b.

String i is said to be interleaving string a and b, if:

len(i) = len(a) + len(b).

i only contains characters present in a or b.

i contains all characters of a. From a, any character a[index] should be added exactly once in i.

i contains all characters of b. From b, any character b[index] should be added exactly once in i.

Order of all characters in individual strings (a and b) is preserved.

****

**Example One**

Input:

a = "123"

b = "456"

i = "123456"

Output: True

**Example Two**

Input:

a = "AAB"

b = "AAC"

i = "AAAABC"

Output: True

**Example Three**

Input:

a = "AAB"

b = "AAC"

i = "AAABAC"

Output: True

**Notes**

Input Parameters: You will be given three strings a, b and i.

Strings can contain:

Small alphabets - a-z

Large alphabets - A-Z

Numbers - 0-9

Output: Return a boolean if i is an interleaving of a and b.

**Constraints:**

● 0

● 0

Brute force recursive solution

First character in i should match first character in a or first character in b.

* If it matches first character in a, try matching second character in i with second character in a or first character in b

* If it matches first character in b, try matching second character in i with second character in b or first character in a

* If it matches none of them, terminate with a false

Hence, keep recursing for the rest of the strings. This is an exponential solution, O(2^(len(a)+len(b))) as you can either pick a character from a or a character from b.

Convention: str[0 : x] = first x chars of str.

We can say that i[0 : (a_i + b_i)] is an interleaving of a[0 : a_i] and b[0 : b_i], if at least one of the below two is true:

1) - i[0 : (a_i + b_i - 1)] should be an interleaving of a[0 : (a_i - 1)] and b[0 : b_i]

and

- a[ai - 1] == i[ai + bi - 1].

or

2) - i[0 : (a_i + b_i - 1)] should be an interleaving of a[0 : a_i] and b[0 : (b_i - 1)]

and

- b[bi - 1] == i[ai + bi - 1].

We can use DP to keep track of the already calculated values. Have a look at the solution for more details.

Space Complexity:

O(len(a) * len(b))

Time Complexity:

O(len(a) * len(b))

Note: Input and Output will already be taken care of.

You are given three strings: a, b and i. Write a function that checks whether i is an interleaving of a and b.

String i is said to be interleaving string a and b, if:

len(i) = len(a) + len(b).

i only contains characters present in a or b.

i contains all characters of a. From a, any character a[index] should be added exactly once in i.

i contains all characters of b. From b, any character b[index] should be added exactly once in i.

Order of all characters in individual strings (a and b) is preserved.

****

**Example One**

Input:

a = "123"

b = "456"

i = "123456"

Output: True

**Example Two**

Input:

a = "AAB"

b = "AAC"

i = "AAAABC"

Output: True

**Example Three**

Input:

a = "AAB"

b = "AAC"

i = "AAABAC"

Output: True

**Notes**

Input Parameters: You will be given three strings a, b and i.

Strings can contain:

Small alphabets - a-z

Large alphabets - A-Z

Numbers - 0-9

Output: Return a boolean if i is an interleaving of a and b.

**Constraints:**

● 0

● 0

Brute force recursive solution

First character in i should match first character in a or first character in b.

* If it matches first character in a, try matching second character in i with second character in a or first character in b

* If it matches first character in b, try matching second character in i with second character in b or first character in a

* If it matches none of them, terminate with a false

Hence, keep recursing for the rest of the strings. This is an exponential solution, O(2^(len(a)+len(b))) as you can either pick a character from a or a character from b.

Convention: str[0 : x] = first x chars of str.

We can say that i[0 : (a_i + b_i)] is an interleaving of a[0 : a_i] and b[0 : b_i], if at least one of the below two is true:

1) - i[0 : (a_i + b_i - 1)] should be an interleaving of a[0 : (a_i - 1)] and b[0 : b_i]

and

- a[ai - 1] == i[ai + bi - 1].

or

2) - i[0 : (a_i + b_i - 1)] should be an interleaving of a[0 : a_i] and b[0 : (b_i - 1)]

and

- b[bi - 1] == i[ai + bi - 1].

We can use DP to keep track of the already calculated values. Have a look at the solution for more details.

Space Complexity:

O(len(a) * len(b))

Time Complexity:

O(len(a) * len(b))

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart