Similar Strings

Easy
0/40
Average time to solve is 20m
profile
Contributed by
2 upvotes
Asked in companies
WalmartAmazonGoldman Sachs

Problem statement

You are given two strings, ‘A’ and ‘B’ each of length ‘N’. Your task is to print 1 if ‘A’ is similar to ‘B’.

Note :

String ‘A’ is said to be similar to string ‘B’ if and only if 
1. ‘A’ is equal to ‘B’.
2. Divide both ‘A’ and ‘B’ into two – two strings ‘A1’, ‘A2’ , ‘B1’ and ‘B2’ such that both of them('A1' and 'A2') have same size. Then at least one of the following must hold true:
   a. ‘A1’ is similar to ‘B1’ and ‘A2’ is similar to ‘B2’.
   b. ‘A1’ is similar to ‘B2’ and ‘A2’ is similar to ‘B1’.
Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains two space-separated strings ‘A’ and ‘B’.

Output Format :

For each test case, print 1 if ‘A’ is similar to ‘B’, else print 0.

The output of each test case will be printed in a separate line.

Constraints :

1 <= T <= 5
1 <=  |A| = |B| = 3000
Both A, B contain only lowercase English letters.

Where |A| and |B| are the length of strings.

Time Limit: 1 sec

Note :

 You do not need to print anything, it has already been taken care of. Just implement the given function.

Sample Input 1 :

2
aa aa
ab ba

Sample Output 1 :

1
1

Explanation Of Sample Input 1 :

Test Case 1 :  
Given A = “aa” and B = “aa” 
Here A and B are equal. So A is similar to B.

Test Case 2 : 
Given A = “ab” = “a” + “b” = A1 + A2
And    B = “ba” = “b” + “a” = B1 + B2
Here A1 is similar to B2 and A2 is similar to B1
So, A is similar to B.

Sample Input 2 :

2
ab cd 
aaca acaa

Sample Output 2 :

0
1

Explanation Of Sample Input 2 :

Test Case 1 :  
Given A = “ab” and B = “cd”. 
We can see that A and B are not similar. 

Test Case 2 : 
Given A = “aaca” and B = “acaa”. 
A = “aa” + “ca”  A1 = “aa” and A2 = “ca” 
B = “ac” + “aa”  B1 = “ac” and B2 = “ca”
Here A1 = B2 So, A1 is similar to B2. 
Now consider A2 = “ca” and B1 =”ac” 
Divide both them into equal size A2 = “c” + “a” and B1 = “a” + “c”. 
We can easily see that A2 and B1 are similar. 
So, we have A1 is similar to B2 and A2 is similar to B1. 
Hence A and B are similar to each other.
Hint

Think of a solution similar to generate all possible combinations.

Approaches (2)
Brute force


 

The idea here is to generate all possible combinations of the dividing of  ‘A’ and ‘B’. So at each step we will make four recursive calls to check either  A1 is similar to B2 and A2 is similar to B1 or A1 is similar to B1 or A2 is similar to B2.

 

Algorithm:

  • If the length of string “A” is odd, then If “A” equals “B”, then return true, else false.
  • Divide “A” into two substrings of the same size, say, “A1” and “A2”.
  • Divide “B” into two substrings of the same size, say, “B1” and “B2”.
  • Make two recursive calls with strings (A1, B1) and (A2, B2). If both of these return true, then return true.
  • Make two recursive calls with strings (A1, B2) and (A2, B1), If both of these return true, then return true.
  • Return false as ‘A’ is not similar to ‘B’.
Time Complexity

O(N ^ 2), where ‘N’ is the length of the given string.

 

We will get recurrence of above code as T(N) = 4 * T(N / 2 ) + O(N) as we are making four recursive calls at each step and each one of them takes O(N) time. 

Solving the above recurrence by master theorem we will get O(N ^ 2).

Space Complexity

O(N ^ 2) , where ‘N’ is the length of the given string

 

We will get recurrence of the above code as T(N) = 4 * T(N / 2 ) + O(N) as we are making four recursive calls at each step and each one of them takes O(N) space as we are creating four new strings of size O(N) each time. 

Solving the above recurrence by master theorem we will get O(N ^ 2).

Code Solution
(100% EXP penalty)
Similar Strings
Full screen
Console