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.


-----Examples-----

Input
7
3
cbc
aba
5
abcaa
cbabb
5
abcaa
cbabz
1
a
a
1
a
b
6
abadaa
adaaba
8
abcabdaa
adabcaba
Output
YES
YES
NO
YES
NO
NO
YES


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

Source: codeforces | Difficulty: HARD
Tags: String algorithms

Amortized analysis

Constructive algorithms


Solutions:
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')
main()


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)])


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	s1 = input().strip()
	s2 = input().strip()
	cnt = {}
	for i in range(n):
		(x, y) = (ord(s1[i]), ord(s2[n - 1 - i]))
		(x, y) = (min(x, y), max(x, y))
		if (x, y) not in cnt:
			cnt[x, y] = 0
		cnt[x, y] += 1
	if all([cnt[key] % 2 == 0 for key in cnt]):
		return 'YES'
	else:
		un = 0
		same = False
		for key in cnt:
			if cnt[key] % 2:
				un += 1
				same = key[0] == key[1]
		return 'YES' if un == 1 and same else 'NO'
for _ in range(int(input())):
	print(solve())


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)])


def putin():
	return map(int, input().split())

def solve():
	n = int(input())
	s = input()
	r = input()
	pairs = []
	for i in range(len(s)):
		pairs.append(tuple(sorted([s[i], r[n - 1 - i]])))
	D = {}
	for elem in pairs:
		if elem in D:
			D[elem] += 1
		else:
			D[elem] = 1
	odd = 0
	for elem in D:
		if D[elem] % 2 == 1:
			if elem[0] != elem[1]:
				return 'NO'
			odd += 1
	return 'YES' if odd < 2 else 'NO'
t = int(input())
for i in range(t):
	print(solve())


def putin():
	return map(int, input().split())

def solv():
	a = int(input())
	x = input()
	R = input()
	pair = []
	for j in range(len(x)):
		pair.append(tuple(sorted([x[j], R[a - 1 - j]])))
	A = {}
	for elem in pair:
		if elem in A:
			A[elem] += 1
		else:
			A[elem] = 1
	odd = 0
	for elem in A:
		if A[elem] % 2 == 1:
			if elem[0] != elem[1]:
				return 'NO'
			odd += 1
	return 'YES' if odd < 2 else 'NO'
Q = int(input())
for J in range(Q):
	print(solv())


from collections import Counter
for i in range(int(input())):
	n = int(input())
	s = input()
	t = input()
	pairs = []
	flag = True
	for i in range(n):
		pairs.append(tuple(sorted((s[i], t[n - i - 1]))))
	x = Counter(pairs)
	odd = 0
	for t in x:
		if x[t] % 2 == 1:
			if t[0] != t[1]:
				print('NO')
				flag = False
				break
			odd += 1
	if flag:
		if odd < 2:
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(t):
	length = int(input())
	s1 = list(input())
	s2 = list(input())
	tmp = dict()
	for j in range(0, length):
		c1 = s1[j]
		c2 = s2[length - j - 1]
		if c2 < c1:
			(c1, c2) = (c2, c1)
		tmp[c1 + c2] = tmp.get(c1 + c2, 0) + 1
	flag = False
	flag_odd = 0
	for x in tmp:
		if tmp[x] % 2 == 1:
			flag_odd += 1
			if length % 2 == 0:
				print('NO')
				flag = True
				break
			elif flag_odd > 1 or x[0] != x[1]:
				print('NO')
				flag = True
				break
	if flag:
		continue
	print('YES')


from collections import defaultdict, Counter
hasher = 10 ** 5

def solve():
	n = int(input())
	s = input()
	t = input()
	hs = defaultdict(int)
	for i in range(n):
		(lt, rt) = (s[i], t[n - 1 - i])
		hs[ord(min(lt, rt)) * hasher + ord(max(lt, rt))] += 1
	ans = 0
	for (x, y) in hs.items():
		if y % 2 == 0:
			continue
		ans += 1
		if x // hasher != x % hasher:
			print('NO')
			return False
	print('YES' if ans <= 1 else 'NO')
for _ in range(int(input())):
	solve()


tc = int(input())
for i in range(tc):
	all_pairs = {}
	s = int(input())
	s1 = input()
	s2 = input()
	for i in range(s):
		k1 = (s1[i], s2[-1 - i])
		k2 = (s2[-1 - i], s1[i])
		if k1 in all_pairs:
			all_pairs[k1] += 1
		else:
			all_pairs[k1] = 1
		if k2 in all_pairs and k2 != k1:
			all_pairs[k2] += 1
		elif k2 != k1:
			all_pairs[k2] = 1
	works = True
	flag = True
	for key in all_pairs:
		if all_pairs[key] % 2 == 1:
			if key[0] == key[1] and flag:
				flag = False
			else:
				works = False
				break
	if works:
		print('YES')
	else:
		print('NO')


from collections import Counter

def one():
	n = int(input())
	s1 = input()
	s2 = input()
	c = Counter(((min(s1[i], s2[-i - 1]), max(s1[i], s2[-i - 1])) for i in range(n)))
	r = [k for (k, v) in c.items() if v % 2]
	return len(r) == 0 or (len(r) == 1 and r[0][0] == r[0][1])
t = int(input())
for i in range(t):
	print('YES' if one() else 'NO')


from collections import Counter

def Pre_Suf():
	num = int(input())
	p = input()
	s = input()
	c = Counter(((min(p[i], s[-i - 1]), max(p[i], s[-i - 1])) for i in range(num)))
	res = [k for (k, v) in c.items() if v % 2]
	return len(res) == 0 or (len(res) == 1 and res[0][0] == res[0][1])
testc = int(input())
for i in range(testc):
	print('YES' if Pre_Suf() else 'NO')


from typing import Counter
for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	map_ = Counter(((min(s1[i], s2[-i - 1]), max(s1[i], s2[-i - 1])) for i in range(n)))
	res = [key for (key, value) in map_.items() if value % 2]
	ans = len(res) == 0 or (len(res) == 1 and res[0][0] == res[0][1])
	print('YES' if ans else 'NO')


import sys
t = int(input())
for _ in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	if s1 == s2:
		print('YES')
		continue
	s2 = s2[::-1]
	d = {}
	for i in range(n):
		temp = (max(ord(s1[i]), ord(s2[i])), min(ord(s1[i]), ord(s2[i])))
		if temp not in d.keys():
			d[temp] = 1
		else:
			d[temp] += 1
	if n % 2 == 0:
		stop = 0
		for j in d.keys():
			if d[j] % 2 == 1:
				stop = 1
				break
		if stop == 1:
			print('NO')
		else:
			print('YES')
	else:
		odd = 0
		stop = 0
		for j in d.keys():
			if d[j] % 2 == 1:
				odd += 1
				if j[0] != j[1] or odd > 1:
					stop = 1
					break
		if stop == 1:
			print('NO')
		else:
			print('YES')


import builtins
tests = int(input())
for it in range(tests):
	n = int(input())
	s1 = input()
	s2 = input()
	d = dict()
	for i in range(n):
		l = (min(s1[i], s2[n - i - 1]), max(s1[i], s2[n - i - 1]))
		if l not in d:
			d[l] = 0
		d[l] += 1
	cnt = 0
	cnt2 = 0
	for i in d:
		if i[0] == i[1] and d[i] % 2 == 1:
			cnt += 1
		if i[0] != i[1] and d[i] % 2 == 1:
			cnt2 = 1
	if cnt2 > 0:
		print('NO')
		continue
	if n % 2 == 0:
		if cnt > 0:
			print('NO')
			continue
		print('YES')
		continue
	if cnt != 1:
		print('NO')
		continue
	print('YES')