Prefixes and Suffixes (Codeforces 1730D)
Tags: Others, strings

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: 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: For each test case, print "YES" if it is possible to make the strings equal, and "NO" otherwise.

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.

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

Sample Outputs:
YES
YES
NO
YES
NO
NO
YES

Solution (Python):
import sys
from collections import defaultdict

def main():
    t = int(sys.stdin.readline()[:-1])
    for _ in range(t):
        n = int(sys.stdin.readline()[:-1])
        s1 = sys.stdin.readline()[:-1]
        s2 = sys.stdin.readline()[:-1]
        ps = defaultdict(int)
        for i in range(n):
            if s1[i] > s2[n - 1 - i]:
                st = (s2[n - 1 - i], s1[i])
            else:
                st = (s1[i], s2[n - 1 - i])
            ps[st] += 1
        (t, flag) = (0, True)
        for (k, v) in ps.items():
            if v & 1:
                t += 1
                if k[0] != k[1]:
                    flag = False
        if t == 0:
            print('YES')
        elif t == 1:
            if flag:
                print('YES')
            else:
                print('NO')
        else:
            print('NO')
if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
for SHDFVBLWSGFVYUV in range(int(input())):
    (SHDFVBLWSGFVYUV, sSHDFVBLWSGFVYUV1, sSHDFVBLWSGFVYUV2) = (input() for SHDFVBLWSGFVYUV in range(3))
    odd = [p for (p, v) in Counter((frozenset((x, y)) for (x, y) in zip(reversed(sSHDFVBLWSGFVYUV1), sSHDFVBLWSGFVYUV2))).items() if v % 2]
    print(('NO', 'YES')[len(odd) == 0 or (len(odd) == 1 and len(odd[0]) == 1)])

Solution (Python):
from collections import Counter
for _ in range(int(input())):
    (_, s1, s2) = (input() for _ in range(3))
    odd = [p for (p, v) in Counter((frozenset((x, y)) for (x, y) in zip(reversed(s1), s2))).items() if v % 2]
    print(('NO', 'YES')[len(odd) == 0 or (len(odd) == 1 and len(odd[0]) == 1)])