Last Updated: 4 Mar, 2021

Similar Strings

Easy

Asked in companies

Solve now

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

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.

Solve now

Approaches

01 Approach

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

Solve now

02 Approach

The idea here is to fact that we are making both strings equal by doing some operations on them. In the end we are getting ‘A’ = ‘B’. So we will find the lexicographically smallest string that can be formed using ‘A’ and ‘B’. If both of them are the same then we will return true, else false.

Algorithm:

Find the lexicographically smallest string of ‘A’ and ‘B’ formed using operations given in the problem, say “SA” and “SB” by calling the ‘smallest’ function.
If ‘SA’ = ‘SB’, then return true else, return false.

Description of smallest function

string smallest( S ) :

If the size of ‘S’ is odd, then return ‘S’.
Divide ‘S’ into two substrings of equal length, say ‘X’ and ‘Y’.
Recursively call the 'smallest’’ function with ‘X’ and ‘Y’ as arguments to get strings ‘S1’ and ‘S2’.
If ‘S1’ > ‘S2’ then return ‘S1 + S2’ else return ‘S2 + S1’ as we are interested in the lexicographically smallest string.

Solve now