Prefixes and Suffixes
Contest: Codeforces Round 823 (Div. 2)
Difficulty rating: 2200
Tags: constructive algorithms, strings, two pointers

You have two strings $$$s_1$$$ and $$$s_2$$$ of length $$$n$$$, consisting of lowercase English letters. You can perform the following operation any (possibly zero) number of times:

- Choose a positive integer $$$1 \leq k \leq n$$$.
- Swap the prefix of the string $$$s_1$$$ and the suffix of the string $$$s_2$$$ of length $$$k$$$.

Is it possible to make these two strings equal by doing described operations?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then the test cases follow.

Each test case consists of three lines.

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the strings $$$s_1$$$ and $$$s_2$$$.

The second line contains the string $$$s_1$$$ of length $$$n$$$, consisting of lowercase English letters.

The third line contains the string $$$s_2$$$ of length $$$n$$$, consisting of lowercase English letters.

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print "YES" if it is possible to make the strings equal, and "NO" otherwise.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case:

- Initially $$$s_1 = \mathtt{cbc}$$$, $$$s_2 = \mathtt{aba}$$$.
- Operation with $$$k = 1$$$, after the operation $$$s_1 = \mathtt{abc}$$$, $$$s_2 = \mathtt{abc}$$$.

In the second test case:

- Initially $$$s_1 = \mathtt{abcaa}$$$, $$$s_2 = \mathtt{cbabb}$$$.
- Operation with $$$k = 2$$$, after the operation $$$s_1 = \mathtt{bbcaa}$$$, $$$s_2 = \mathtt{cbaab}$$$.
- Operation with $$$k = 3$$$, after the operation $$$s_1 = \mathtt{aabaa}$$$, $$$s_2 = \mathtt{cbbbc}$$$.
- Operation with $$$k = 1$$$, after the operation $$$s_1 = \mathtt{cabaa}$$$, $$$s_2 = \mathtt{cbbba}$$$.
- Operation with $$$k = 2$$$, after the operation $$$s_1 = \mathtt{babaa}$$$, $$$s_2 = \mathtt{cbbca}$$$.
- Operation with $$$k = 1$$$, after the operation $$$s_1 = \mathtt{aabaa}$$$, $$$s_2 = \mathtt{cbbcb}$$$.
- Operation with $$$k = 2$$$, after the operation $$$s_1 = \mathtt{cbbaa}$$$, $$$s_2 = \mathtt{cbbaa}$$$.

In the third test case, it's impossible to make strings equal.

Example input:
7
3
cbc
aba
5
abcaa
cbabb
5
abcaa
cbabz
1
a
a
1
a
b
6
abadaa
adaaba
8
abcabdaa
adabcaba

Example output:
YES
YES
NO
YES
NO
NO
YES

Editorial:
If you reflect the second string and see what happens, it is easy to see that the elements at the same positions in both strings after any action remain at the same positions relative to each other. Let's combine them into unsorted pairs and treat these pairs as single objects. Now we need to compose a palindrome from these objects. This is always possible with the help of these actions, if there is a palindrome consisting of these objects (pay attention to odd palindromes, there must be a pair of the form (a, a) in the center).
Proof of possibility:
Let's make an array of pairs, in one action we expand some prefix of this array and the elements in the pairs of this prefix are swapped. Let's prove that we can change the order of the pairs in the array as we like. We will build from the end. Let all the pairs after position $$$i$$$ already stand as we want, and now the pair that we want to place in position $$$i$$$ at position $$$j \leq i$$$. Let's do the following:
$$$1.$$$ $$$k = j$$$ — will move the pair from position $$$j$$$ to the beginning.
$$$2*.$$$ $$$k = 1$$$ — swap elements within a pair if needed (so pairs are considered unsorted).
$$$3.$$$ $$$k = i$$$ — move the pair from the beginning to position $$$i$$$.
(* the $$$2$$$ action is optional if you don't want to change the order of the elements in the pair)
With this construction, we can get any permutation of these pairs and a palindrome, if it is possible. If you divide the final palindrome into two strings and expand the second one back, you get the first string.
Example:
From the test suite from the condition:
$$$s_1 = \mathtt{bbcaa}$$$, $$$s_2 = \mathtt{cbaab}$$$, expanded $$$s_2 = \mathtt{baabc}$$$.
Couples:
$$$\mathtt{(b, b)}$$$, $$$\mathtt{(b, a)}$$$, $$$\mathtt{(c, a)}$$$, $$$\mathtt{(a, b)}$$$, $$$\ mathtt{(a, c)}$$$.
Pairs unordered:
$$$\mathtt{(b, b)}$$$, $$$\mathtt{(a, b)} \cdot 2$$$, $$$\mathtt{(a, c)} \cdot 2$$$.
Pairs in a palindrome:
$$$\mathtt{(a, b)}$$$, $$$\mathtt{(a, c)}$$$, $$$\mathtt{(b, b)}$$$, $$$\mathtt{(a, c)}$$$, $$$\mathtt{(a, b)}$$$.
Real couples:
$$$\mathtt{(a, b)}$$$, $$$\mathtt{(a, c)}$$$, $$$\mathtt{(b, b)}$$$, $$$\mathtt{(c, a)}$$$, $$$\mathtt{(b, a)}$$$.
Strings: $$$s_1 = \mathtt{aabcb}$$$ expanded $$$s_2 = \mathtt{bcbaa}$$$, $$$s_2 = \mathtt{aabcb}$$$.
!!! The pair $$$\mathtt{(b, b)}$$$ !!!