Equivalent Strings

Interview

Time limit2sMemory limit512 MB

Summary

Decide whether two equal-length strings are equivalent under recursive splitting and optional swap of halves.

Level: Medium6 of 10
Topics: Divide and conquer, String, Recursion, Sorting
Solved: No attempts yet

Problem

Two strings a and b of the same length are called equivalent if one of the two conditions below holds.

The two strings are exactly the same.
The length is even, and after cutting a into two pieces a1, a2 of equal length and cutting b into two pieces b1, b2 of equal length, one of the two cases below holds.
1. a1 is equivalent to b1, and a2 is equivalent to b2.
2. a1 is equivalent to b2, and a2 is equivalent to b1.

Given two strings a and b, decide whether they are equivalent.

Input

The first line contains the string a and the second line contains the string b. The two strings have the same length, which is at least 1 and at most 200,000. Both strings consist of the 26 lowercase English letters only.

Output

Print YES if a and b are equivalent, and NO otherwise.

Hint

In the first example a = "aaba" splits into a1 = "aa" and a2 = "ba", while b = "abaa" splits into b1 = "ab" and b2 = "aa". The piece a2 = "ba" splits into "b" and "a", and b1 = "ab" splits into "a" and "b", so the second case of condition 2 makes a2 and b1 equivalent. The pieces a1 = "aa" and b2 = "aa" are exactly the same, so the second case of condition 2 applies again and a and b are equivalent.

In the second example a = "aabb" splits into a1 = "aa" and a2 = "bb". Each piece uses a single letter, so the only strings equivalent to a are "aabb" and "bbaa".

Examples7

Example 1
Input
```
aaba
abaa
```
Expected output
```
YES
```
Example 2
Input
```
aabb
abab
```
Expected output
```
NO
```
Example 3
Input
```
a
a
```
Expected output
```
YES
```
Example 4
Input
```
a
z
```
Expected output
```
NO
```
Example 5
Input
```
aabb
bbaa
```
Expected output
```
YES
```
Example 6
Input
```
abcdef
defabc
```
Expected output
```
YES
```
Example 7
Input
```
abcdef
abcfed
```
Expected output
```
NO
```