Mario was going to gift Princess Peach a string S of even length N. 

Mario was clumsy and thus, broke the string in the middle. He now has two strings A and B such that A = S[1, \frac{N}{2}] and B = S[\frac{N}{2} + 1, N]. 

Mario is not sure about the order in which he should join the strings A and B to get the string S. Thus, he joins the strings in any random order. Find whether it is guaranteed that Mario will get the same string S if he joins the strings A and B in any order.

Note that S[L, R] denotes a substring of string S starting at index L and having a length (R - L + 1).

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input:
- The first line of each test case contains N - the length of the initial string S.
- The second line contains the string S.

------ Output Format ------ 

For each test case, print YES if it is guaranteed that Mario will get the same string S irrespective of the order in which he joins the strings A and B and NO otherwise. 

You may print each character of the string in uppercase or lowercase (for example, the strings YES, yEs, yes, and yeS will all be treated as identical).

------ Constraints ------ 

$1 ≤ T ≤ 3000$
$1 ≤ N ≤ 1000$
$N$ is even.
$S$ consists of lowercase english alphabets.

----- Sample Input 1 ------ 
4
6
abcabc
6
abcdef
4
aaaa
4
baab
----- Sample Output 1 ------ 
YES
NO
YES
NO

----- explanation 1 ------ 
Test case $1$: On breaking, the string $S$ gives $A = abc$ and $B = abc$. Thus, joining it in either way $(AB$ or $BA)$, would give the same string $S$.

Test case $2$: On breaking, the string $S$ gives $A = abc$ and $B = def$. Joining it as $BA$ would give the string $defabc$ which is not equal to string $S$.

Test case $3$: On breaking, the string $S$ gives $A = aa$ and $B = aa$. Thus, joining it in either way $(AB$ or $BA)$, would give the same string $S$.

Test case $4$: On breaking, the string $S$ gives $A = ba$ and $B = ab$. Joining it as $BA$ would give the string $abba$ which is not equal to string $S$.

Source: codechef | Difficulty: EASY
Tags: String algorithms

Data structures


Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	a = s[:n // 2]
	b = s[n // 2:]
	if a == b:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	x = int(input())
	v = input()
	c = len(v) / 2
	c = int(c)
	b = v[:c]
	n = v[c:]
	z = 0
	q = 0
	for i in b:
		if i == n[z]:
			q = q + 1
		z = z + 1
	if q == len(b):
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	a = s[0:int(n / 2)]
	b = s[int(n / 2):n]
	if a + b == s and b + a == s:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	n = int(input())
	s = input()
	c = 0
	for i in range(n // 2):
		if s[i] == s[n // 2 + i]:
			c += 1
	if c == n // 2:
		print('YES')
	else:
		print('NO')
	t = t - 1


for i in range(int(input())):
	n = int(input())
	m = input()
	a = m[:n // 2]
	b = m[n // 2:]
	if a == b:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	half = n // 2
	flag = True
	for i in range(half):
		if s[i] != s[i + half]:
			flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	x = int(n / 2)
	s_half1 = s[:x]
	s_half2 = s[x:]
	if s_half2 + s_half1 == s:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	c = 0
	(l, m) = ([], [])
	k = int(input())
	s = input()
	for i in range(0, k // 2):
		l.append(s[i])
	for i in range(k // 2, k):
		m.append(s[i])
	if l == m:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	if s[0:n // 2] == s[n // 2:]:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	l = int(input())
	s = input()
	s1 = ''
	s2 = ''
	x = len
	s1 = s[:len(s) // 2]
	s2 = s[len(s) // 2:]
	if s1 + s2 == s and s2 + s1 == s:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	k = int(input())
	s = input()
	d = int(len(s) / 2)
	g = s[:d]
	h = s[d:]
	if h + g == s:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if s[0:int(n / 2)] == s[int(n / 2):n]:
		print('YES')
	else:
		print('NO')


for j in range(int(input())):
	n = int(input())
	s = input()
	A = s[:len(s) // 2]
	B = s[len(s) // 2:]
	if (A + B and B + A) == s:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = str(input())
	l = []
	m = []
	for i in range(n // 2):
		l.append(s[i])
	for i in range(n // 2, n):
		m.append(s[i])
	if l == m:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = list(input())
	g = []
	f = []
	for i in range(0, n // 2):
		g.append(s[i])
	for i in range(n // 2, n):
		f.append(s[i])
	if g == f:
		print('YES')
	else:
		print('NO')


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		s = input()
		str1 = ''
		str2 = ''
		for i in range(n):
			if i < n / 2:
				str1 = str1 + str(s[i])
			else:
				str2 = str2 + str(s[i])
		if s == str1 + str2 and s == str2 + str1:
			print('YES')
		else:
			print('NO')
main()


for t in range(int(input())):
	n = int(input())
	s = input()
	s1 = s[0:len(s) // 2]
	s2 = s[len(s) // 2:len(s)]
	if s2 + s1 == s:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	S = str(input())
	n = int(N / 2)
	A = S[0:n]
	B = S[n:N]
	if A + B and B + A == S:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	N = int(input())
	S = str(input())
	a = S[:N // 2]
	b = S[N // 2:]
	print('YES') if str(a) == str(b) else print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	M = int(len(S)) / 2
	length = len(S)
	middle = length // 2
	F1 = S[:middle]
	F2 = S[middle:]
	if F1 == F2:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	c = 0
	(a, b) = ([], [])
	n = int(input())
	s = input()
	for i in range(0, n // 2):
		a.append(s[i])
	for i in range(n // 2, n):
		b.append(s[i])
	if a == b:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = s[0:len(s) // 2]
	b = s[len(s) // 2:]
	if a == b:
		print('YES')
	else:
		print('NO')


def solve(valN, val):
	if val[:int(valN / 2)] == val[int(valN / 2):]:
		return 'YES'
	else:
		return 'NO'
n = int(input())
for _ in range(n):
	valN = int(input())
	val = input()
	print(solve(valN, val))


t = int(input())
for _ in range(t):
	n = int(input())
	s = str(input())
	s = list(s)
	if s[:n // 2] == s[n // 2:n]:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	input_str = input()
	str_1 = input_str[:int(n / 2)]
	str_2 = input_str[int(n / 2):]
	if str_2 + str_1 == str_1 + str_2:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	N = int(input())
	S = input()
	A = S[0:N // 2]
	B = S[N // 2:]
	c = B + A
	if c == S:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(1, n + 1):
	x = int(input())
	s = str(input())
	(c, v) = (s[:len(s) // 2], s[len(s) // 2:])
	if (c + v and v + c) == s:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	if s[:n // 2] + s[n // 2:] == s and s[n // 2:] + s[:n // 2] == s:
		print('YES')
	else:
		print('NO')
	t -= 1


for ______cases______ in range(int(input())):
	N = int(input())
	S = input()
	print('YES' if S[N // 2:] + S[:N // 2] == S else 'NO')


for i in range(int(input())):
	l = int(input())
	s = input()
	res = ''
	n = l // 2
	res = s[n:] + s[0:n]
	if res == s:
		print('YES')
	else:
		print('NO')


for case in range(int(input())):
	N = int(input())
	S = input()
	A = S[0:N // 2]
	B = S[N // 2:N]
	if A + B == S and B + A == S:
		print('YES')
	else:
		print('NO')


def stri(a, b):
	c = a // 2
	k = b[0:c]
	t = b[c:]
	x = t + k
	if x == b:
		print('YES')
	else:
		print('NO')
n = int(input())
for i in range(n):
	a = int(input())
	b = input()
	stri(a, b)


def fun(s):
	(i, j) = (0, len(s) // 2)
	while i < len(s) // 2 and j < len(s):
		if s[i] == s[j]:
			i = i + 1
			j = j + 1
		else:
			return 'NO'
	return 'YES'
t = int(input())
for i in range(0, t):
	n = int(input())
	s = input()
	print(fun(s))


t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	ans = s[:len(s) // 2]
	ans1 = s[len(s) // 2:]
	if n % 2 == 0:
		if ans == ans1:
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	a = n // 2
	b = s[:a]
	c = s[a:n]
	if b == c:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	a = int(input())
	b = input()
	if b[:a // 2] == b[a // 2:]:
		print('YES')
	else:
		print('NO')


def the(n, s):
	if s[:int(n / 2)] == s[int(n / 2):]:
		return 'YES'
	else:
		return 'NO'
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	v = the(n, s)
	print(v)


t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	m = int(n / 2)
	if s[m:] == s[:m]:
		print('YES')
	else:
		print('NO')