Anton loves creating strings!

Anton now wants to create a string S following some specific rules. They are as follows:

Initially, S is empty. Then, Anton can perform two types of operations on S:
1. Choose a lowercase Latin character (an element of \{a, b, c, \ldots, z\}) and append it to S. For example, if currently S = \texttt{clap}, Anton can turn it into one of \{\texttt{clapa}, \texttt{clapb}, \ldots, \texttt{clapz}\}.
2. Append a copy of S to itself. For example, if currently S = \texttt{clap}, Anton can turn it into \texttt{clapclap}.

However, Anton doesn't want to perform operation 1 twice in a row.

You are given a string A consisting of the lowercase Latin alphabet. Is it possible for Anton to create A using his operations any number of times?

------ 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 a single integer N, the length of the string A.
- The second line of each test case contains a string A of length N.

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

For each test case, output on a new line the answer — YES if Anton can create A using his operations, and NO otherwise.

Each character of the output may be printed in either uppercase or lowercase. For example, the strings YES, yes, and YeS will all be treated as identical.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{6}$
$A$ consists of only lowercase Latin characters
- The sum of $N$ across all test cases won't exceed $10^{6}$

----- Sample Input 1 ------ 
4
2
ab
3
oof
6
aabaab
5
eevee

----- Sample Output 1 ------ 
NO
YES
YES
NO

----- explanation 1 ------ 
Test case $1$: Anton can create $\texttt{a}$ by starting from the empty string and appending $\texttt{a}$ using operation $1$. However, there is no way to create $\texttt{ab}$ — the only way to do so is to use operation $1$ again and append $\texttt{b}$; but this is not allowed.

Test case $2$: Anton can create $\texttt{oof}$ from the empty string as follows:
- Use operation $1$ to append $\texttt{o}$. The current string is $\texttt{o}$.
- Use operation $2$ to append the string to itself. The current string is $\texttt{oo}$.
- Use operation $1$ to append $\texttt{f}$. The string is now $\texttt{oof}$, as required.

Test case $3$: $\texttt{aabaab}$ can be created as follows:
- Append $\texttt{a}$ to the empty string. The current string is $\texttt{a}$.
- Use operation $2$. The current string is $\texttt{aa}$.
- Append $\texttt{b}$ with operation $1$. The current string is $\texttt{aab}$.
- Use operation $2$. The current string is $\texttt{aabaab}$, and we are done.

Test case $4$: It can be shown that no sequence of operations will allow Anton to create the string $\texttt{eevee}$.

Difficulty: MEDIUM
Tags: Implementation

Constructive algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	s = input()
	while len(s) > 0:
		if len(s) & 1 != 0:
			s = s[:-1]
		else:
			m = len(s) // 2
			if s[:m] == s[m:]:
				s = s[:m]
			else:
				break
	if len(s) == 0:
		print('YES')
	else:
		print('NO')


def isDouble(string):
	s = len(string)
	if s % 2 == 0 and string[:s // 2] == string[s // 2:]:
		return True
	else:
		return False
T = int(input())
for _ in range(T):
	N = int(input())
	A = input().strip()
	s = A
	possible = True
	while len(s) > 1:
		if isDouble(s[:-1]) or isDouble(s):
			s = s[:len(s) // 2]
		else:
			possible = False
			break
	if possible:
		print('YES')
	else:
		print('NO')


def checkDouble(s, idx, n):
	for i in range(idx):
		if i + idx >= n:
			return 0
		if s[i] != s[i + idx]:
			return 0
	return 1

def ans(n, s):
	while n > 0:
		n = len(s)
		if n % 2 == 0:
			if s[:n // 2] != s[n // 2:]:
				return 'NO'
			else:
				s = s[:n // 2]
		else:
			s = s[:n - 1]
	return 'YES'
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	print(ans(n, s))


for i in range(int(input())):
	n = int(input())
	s = input()
	flag = False
	while n > 0:
		n = len(s)
		if len(s) % 2 == 0:
			if s[n // 2:] == s[:n // 2]:
				s = s[:n // 2]
			else:
				flag = True
				break
		else:
			n = n - 1
			s = s[:n]
			if s[n // 2:] == s[:n // 2]:
				s = s[:n // 2]
			else:
				flag = True
				break
	if flag:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	f = False
	while s:
		n = len(s)
		if n % 2 == 1:
			s = s[:n - 1]
			n -= 1
		if s[:n // 2] == s[n // 2:]:
			s = s[:n // 2]
		else:
			print('NO')
			f = True
			break
	if not f:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	s = input()
	flag = False
	while s:
		n = len(s)
		if n % 2 == 1:
			s = s[:n - 1]
			n -= 1
		if s[:n // 2] == s[n // 2:]:
			s = s[:n // 2]
		else:
			print('NO')
			flag = True
			break
	if not flag:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = True
	while n > 0:
		if n % 2 == 0:
			if s[:n // 2] == s[n // 2:n]:
				ans = True
			else:
				ans = False
				break
			n = n // 2
		else:
			n = n - 1
	if ans == True:
		print('YES')
	else:
		print('NO')


def canCreateString(s, n):
	ans = True
	while n > 0:
		if n % 2 == 1:
			n = n - 1
		else:
			mid = int(n / 2)
			if s[0:mid] != s[mid:n]:
				ans = False
				break
			n = mid
	if ans == True:
		print('YES')
	else:
		print('NO')
t = int(input())
while t != 0:
	n = int(input())
	s = input()
	canCreateString(s, n)
	t = t - 1


def fun(s):
	if len(s) % 2 == 1:
		return (1, s[:-1])
	if s[:len(s) // 2] == s[len(s) // 2:]:
		return (0, s[:len(s) // 2])
	return (1, s[:-1])
for _ in range(int(input())):
	l = int(input())
	s = input()
	sum = 0
	ch = True
	while len(s) > 0:
		(i, s) = fun(s)
		sum = (sum + i) * i
		if sum == 2:
			print('NO')
			ch = False
			break
	if ch:
		print('YES')


for i in range(int(input())):
	n = int(input())
	a = input()
	key = 0
	l = []
	for i in a:
		l.append(i)
	while True:
		if len(l) == 1:
			print('YES')
			break
		if len(l) % 2 == 1:
			if key == 1:
				print('NO')
				break
			key = 1
			l.pop()
		elif l[0:len(l) // 2] == l[len(l) // 2:len(l)]:
			key = 0
			l = l[0:len(l) // 2]
		else:
			print('NO')
			break


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	flag = 0
	while n > 1:
		if n % 2 == 0:
			if s[0:n // 2] == s[n // 2:]:
				n = n // 2
				s = s[0:n]
			else:
				flag = 1
				break
		elif n % 2 == 1:
			n = n - 1
			s = s[0:n]
	if flag == 0:
		print('YES')
	else:
		print('NO')


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()

def solve():
	n = ri()
	s = rs()
	while s:
		if len(s) & 1:
			s = s[:-1]
		else:
			mid = len(s) // 2
			if s[:mid] == s[mid:]:
				s = s[:mid]
			else:
				return 'NO'
	return 'YES'

def main():
	for _ in range(ri()):
		print(solve())
main()


T = int(input())
for i in range(T):
	N = int(input())
	A = input()
	flag = 0
	while len(A) > 1:
		if len(A) % 2 == 0:
			if A[:len(A) // 2] == A[len(A) // 2:]:
				A = A[:len(A) // 2]
			else:
				flag = 1
				break
		else:
			A = A[:-1]
	if flag == 1:
		print('NO')
	elif len(A) == 1:
		print('YES')


def checkValidity(stringToBeFormed):
	length = len(stringToBeFormed)
	if length < 2:
		return True
	if stringToBeFormed[0] != stringToBeFormed[1]:
		return False
	if length % 2 == 0:
		newLen = int(length / 2)
		if stringToBeFormed[0:newLen] == stringToBeFormed[newLen:]:
			return True and checkValidity(stringToBeFormed[0:newLen])
	if length % 2 == 1:
		newLen = int((length - 1) / 2)
		if stringToBeFormed[0:newLen] == stringToBeFormed[newLen:newLen * 2]:
			return True and checkValidity(stringToBeFormed[0:newLen])
	return False
for _ in range(int(input())):
	length = int(input())
	stringToBeFormed = input()
	result = checkValidity(stringToBeFormed)
	if result:
		print('YES')
	else:
		print('NO')


T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	while len(s) > 0:
		if len(s) % 2 != 0:
			s = s[:-1]
		else:
			ans = len(s) // 2
			if s[:ans] == s[ans:]:
				s = s[:ans]
			else:
				break
	if len(s) == 0:
		print('YES')
	else:
		print('NO')


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


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


def sent(str, n):
	while n > 1:
		half = n // 2
		(a, b) = (str[0:half], str[half:n])
		if n % 2 == 0:
			if a == b:
				n = half
			else:
				return 0
		elif a == b[0:half]:
			n = half
		else:
			return 0
	return 1
n = int(input())
for _ in range(n):
	ln = int(input())
	st = input()
	if sent(st, ln):
		print('YES')
	else:
		print('NO')


def fib():
	n = int(input())
	s = input()
	newS = s
	le = len(newS)
	while le:
		if le % 2 == 1:
			newS = newS[:-1]
		else:
			mid = le // 2
			if newS[0:mid] == newS[mid:]:
				newS = newS[0:mid]
			else:
				print('NO')
				return
		le = len(newS)
	print('YES')
n = int(input())
for i in range(n):
	fib()


import sys

def test_string(target: str):
	while len(target) > 0:
		if len(target) % 2 == 0:
			if target[:len(target) // 2] == target[len(target) // 2:]:
				target = target[len(target) // 2:]
			else:
				return False
		else:
			target = target[:-1]
	return True
n = int(sys.stdin.readline())
for _ in range(n):
	l = int(sys.stdin.readline())
	target = sys.stdin.readline().strip()
	print('YES' if test_string(target) else 'NO')


def checkString(str, n):
	while n > 1:
		halfLen = n // 2
		(a, b) = (str[0:halfLen], str[halfLen:n])
		if n % 2 == 0:
			if a == b:
				n = halfLen
			else:
				return False
		elif a == b[0:halfLen]:
			n = halfLen
		else:
			return False
	return True
n = int(input())
for _ in range(n):
	ln = int(input())
	st = input()
	if checkString(st, ln):
		print('YES')
	else:
		print('NO')


def solve(s):
	if len(s) <= 1:
		return True
	if len(s) % 2:
		return solve(s[:-1])
	else:
		n = len(s)
		return s[:n // 2] == s[n // 2:] and solve(s[n // 2:])
for _ in range(int(input())):
	n = int(input())
	s = str(input())
	print('YES') if solve(s) else print('NO')


def solve(s):
	if not s:
		return True
	n = len(s)
	if n == 1:
		return True
	if n % 2:
		return solve(s[:-1])
	mid = n // 2
	if s[:mid] == s[mid:]:
		return solve(s[:mid])
	return False
for _ in range(int(input())):
	trash = input()
	s = list(input().strip())
	print('YES' if solve(s) else 'NO')


for _ in range(int(input())):
	n = int(input())
	a = input()
	flag = 1
	while len(a) != 1:
		if len(a) % 2 != 0:
			a = a[:len(a) - 1]
		elif a[:len(a) // 2] == a[len(a) // 2:len(a)]:
			a = a[:len(a) // 2]
		else:
			flag = 0
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


t1 = int(input())
while t1 > 0:
	n = int(input())
	t = input()
	f = 1
	while len(t) != 1:
		if len(t) % 2 == 1:
			t = t[:len(t) - 1]
		elif t[:len(t) // 2] == t[len(t) // 2:len(t)]:
			t = t[:len(t) // 2]
		else:
			f = 0
			break
	if f == 1:
		print('YES')
	else:
		print('NO')
	t1 -= 1


t = int(input())
while t:
	n = int(input())
	a = input().strip()
	flag = 1
	i = n - 1
	while i > -1:
		if len(a[:i + 1]) & 1 and flag:
			i -= 1
			flag = 0
		elif len(a[:i + 1]) & 1 == 0 and a[:i // 2 + 1] == a[i // 2 + 1:i + 1]:
			flag = 1
			i = i // 2
		else:
			break
	if i < 0:
		print('YES')
	else:
		print('NO')
	t -= 1


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


for _ in range(int(input())):
	N = int(input())
	A = input()
	res = 1
	while N:
		if N & 1:
			N -= 1
			A = A[:-1]
		else:
			n = N // 2
			if A[:n] == A[n:]:
				A = A[:n]
				N = n
			else:
				res = 0
				break
	if res:
		print('YES')
	else:
		print('NO')


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	for i in range(len(s)):
		if len(s) % 2 == 1:
			s = s[:-1]
		else:
			k = len(s) // 2
			if s[:k] == s[k:]:
				s = s[:k]
			else:
				break
	print('YES' if len(s) == 0 else 'NO')


for t in range(int(input())):
	l = int(input())
	A = str(input())
	ans = 1
	while l > 0:
		if l % 2 == 1:
			l -= 1
		else:
			mid = int(l / 2) - 1
			a = A[0:mid + 1]
			b = A[mid + 1:mid + 1 + len(a)]
			if a == b:
				l = int(l / 2)
			else:
				ans = 0
				break
	if ans:
		print('YES')
	else:
		print('NO')


import math

def aa(d, a):
	if len(d) == 1 or len(d) == 0:
		return 'YES'
	elif len(d) == 2:
		if d[0] == d[1]:
			return 'YES'
	elif len(d) % 2 == 0:
		if d[:len(d) // 2] == d[len(d) // 2:]:
			a = aa(d[:len(d) // 2], a)
	else:
		d = d[:-1]
		b = len(d)
		if d[:b // 2] == d[b // 2:]:
			a = aa(d[:b // 2], a)
	return a
for i in range(int(input())):
	n = int(input())
	d = input()
	print(aa(d, 'NO'))


for _ in range(int(input())):
	n = int(input())
	a = input()
	lastop = 1 if n % 2 == 1 else 2
	possible = True
	while n > 0:
		if lastop == 1:
			a = a[:n - 1]
			n -= 1
			lastop = 2
			continue
		if lastop == 2:
			if a[:n // 2] != a[n // 2:]:
				possible = False
				break
			a = a[:n // 2]
			n = n // 2
			lastop = 1 if n % 2 == 1 else 2
			continue
	print('YES' if possible else 'NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	while n > 0:
		if n % 2 == 0 and s[:n // 2] != s[n // 2:n]:
			break
		if n % 2 == 1:
			n -= 1
		else:
			n //= 2
	else:
		print('YES')
		continue
	print('NO')


test = int(input())
while test != 0:
	n = int(input())
	string = input()
	correct = True
	while len(string) != 0:
		if len(string) % 2 == 1:
			string = string[:-1]
		elif string[:len(string) // 2] == string[len(string) // 2:]:
			string = string[:len(string) // 2]
		else:
			correct = False
			print('NO')
			break
	if correct:
		print('YES')
	test -= 1


import sys
import os
import math
import collections
T = int(input())
for _ in range(T):
	N = int(input())
	A = input()
	while len(A):
		if len(A) % 2:
			B = ''
			for i in range((len(A) - 1) // 2):
				B += A[i]
			C = ''
			for i in range((len(A) - 1) // 2, len(A) - 1):
				C += A[i]
			if B != C:
				break
			A = B
		else:
			B = ''
			for i in range(len(A) // 2):
				B += A[i]
			C = ''
			for i in range(len(A) // 2, len(A)):
				C += A[i]
			if B != C:
				break
			A = B
	if len(A) == 0:
		print('YES')
	else:
		print('NO')


from sys import setrecursionlimit
setrecursionlimit(100000000)

def solve(A, N):
	if len(A) == 2:
		if A[0] != A[1]:
			return False
		return True
	elif len(A) == 1:
		return True
	else:
		firstHalf = A[:N // 2]
		secondHalf = A[N // 2:N if N % 2 == 0 else N - 1]
		if firstHalf != secondHalf:
			return False
		return solve(firstHalf, N // 2 - 1 if N // 2 & 1 else N // 2) and solve(secondHalf, N // 2 - 1 if N // 2 & 1 else N // 2)

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		S = input()
		if N == 1:
			print('YES')
		else:
			print('YES' if solve(S[:N - 1 if N & 1 else N], N - 1 if N & 1 else N) else 'NO')
main()


N = int(input())

def can_create(s: str) -> bool:
	i = len(s) - 1
	can_append = True
	while i != -1:
		is_odd = i % 2 == 0
		if is_odd and can_append:
			can_append = False
			i -= 1
		elif not is_odd and s[:(i + 1) // 2] == s[(i + 1) // 2:i + 1]:
			i -= (i + 1) // 2
			can_append = True
		else:
			return False
	return True
for _ in range(N):
	input()
	print('YES' if can_create(input().strip()) else 'NO')


import sys
from itertools import islice
for s in islice(sys.stdin, 2, None, 2):
	n = len(s) - 1
	r = 'YES'
	while n > 1:
		n //= 2
		if s[:n] != s[n:n + n]:
			r = 'NO'
			break
	print(r)


T = int(input())
vector = lambda x, t: [t(num) for num in x.split()]
global cnt
cnt = 0

def check(S, clip=False, delete=False):
	if not S:
		return True
	if len(S) & 1:
		if clip:
			return False
		elif check(S[:-1], True, False):
			return True
		else:
			return False
	elif S[:len(S) // 2] == S[len(S) // 2:] and check(S[:len(S) // 2], False, True):
		return True
	return False
for _ in range(T):
	n = int(input())
	S = input()
	print('YES' if check(S) else 'NO')


ans = ''
for _ in range(int(input())):
	n = int(input())
	s = input()
	if n == 1:
		ans += 'YES\n'
		continue
	if s[0] != s[1]:
		ans += 'NO\n'
		continue
	i = n - 1
	flag = n % 2 == 1
	poss = True
	while i >= 0:
		if (i + 1) % 2 == 0:
			if s[:(i + 1) // 2] == s[(i + 1) // 2:i + 1]:
				i = (i - 1) // 2
				flag = True
			else:
				poss = False
				break
		elif flag:
			i -= 1
			flag = False
		else:
			poss = False
			break
	if poss:
		ans += 'YES\n'
	else:
		ans += 'NO\n'
print(ans)


testcases = int(input())
for eachcase in range(testcases):
	n = int(input())
	string = input()
	while n != 0:
		if n & 1:
			n = n - 1
		elif string[0:n // 2] == string[n // 2:n]:
			n = n // 2
		else:
			break
	if n == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	flag = True
	while flag:
		if len(s) % 2 == 0:
			front = s[:int(len(s) / 2)]
			back = s[int(len(s) / 2):]
			if front == back:
				s = front
			else:
				flag = False
		else:
			s = s[:int(len(s)) - 1]
		if s == '':
			break
	if flag:
		print('YES')
	else:
		print('NO')


def func(s):
	flag = 1
	while len(s) != 0:
		if len(s) % 2 == 0:
			if s[0:len(s) // 2] == s[len(s) // 2:]:
				s = s[0:len(s) // 2]
			else:
				flag = 0
				break
		else:
			s = s[:len(s) - 1]
	return flag
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	ans = func(s)
	if ans == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for __ in range(t):
	n = int(input())
	s = input()
	flag = True
	while n > 0:
		if n % 2 != 0:
			n -= 1
		else:
			mid = n // 2
			x = list(s[0:mid])
			y = list(s[mid:n])
			if x == y:
				n = n // 2
			else:
				flag = False
				break
	if flag:
		print('YES')
	else:
		print('NO')


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

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())

def chk(flag):
	if flag:
		print('YES')
	else:
		print('NO')
for T in range(int(input())):
	n = ni()
	s = si()
	flag = True
	i = n - 1
	while i != 0:
		if (i + 1) % 2 == 1:
			i -= 1
		elif s[:(i + 1) // 2] == s[(i + 1) // 2:i + 1]:
			i //= 2
		else:
			flag = False
			break
	chk(flag)