Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

You are given a string $S$ with length $N$. Determine if it is possible to find two non-empty strings $A$ and $B$ which satisfy the following conditions:
$A + B = S$, where $+$ denotes string concatenation
$B$ is a substring of $A$

Note: $B$ is a substring of $A$ if $B$ can be obtained from $A$ by deleting several (possibly zero) characters from the beginning and several (possibly zero) characters from the end. For example, "ab" is a substring of "cabd", but "ad" is not.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains a single string $S$.

------  Output ------
For each test case, print a single line containing the string "YES" if it is possible to find strings $A$ and $B$ satisfying the given conditions or "NO" otherwise (without quotes).

------  Constraints ------
$1 ≤ T ≤ 10^{4}$
$2 ≤ N ≤ 10^{5}$
$|S| = N$
$S$ contains only lowercase English letters
the sum of $N$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
5

6

cabdab

21

yourcrushlovesyouback

16

wubbalubbadubdub

5

split

7

splitit
----- Sample Output 1 ------ 
YES

NO

YES

NO

YES
----- explanation 1 ------ 
Example case 1: We can choose "cabd" as $A$ and "ab" as $B$. We can see that $A + B = S$ and $B$ is a substring of $A$.

Example case 2: It is impossible to find two strings which satisfy the constraints. For example, when $A$ is "yourcrushlovesyou" and $B$ is "back", then $A + B = S$, but $B$ is not a substring of $A$.

Example case 3: We can choose "wubbalubbadub" as $A$ and "dub" as $B$.

Source: codechef | Difficulty: EASY
Tags: String algorithms

Constructive algorithms

Data structures

Ad-hoc


Solutions:
for _ in range(int(input())):
	n = int(input())
	s = input()
	k = s[-1:]
	s = s[:-1]
	if k in s:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = str(input())
	if s.count(s[-1]) > 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = s[0:len(s) - 1]
	r = s[len(s) - 1:]
	if r in a:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	l = int(input())
	s = input()
	a = s[0:len(s) - 1]
	b = s[len(s) - 1:len(s)]
	if b in a:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	A = S[0:N - 1]
	B = S[N - 1]
	if B in A:
		print('YES')
	else:
		print('NO')


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


def test():
	n = int(input())
	s = input()
	for i in range(n - 1):
		if s[i] == s[n - 1]:
			print('YES')
			return 0
	print('NO')
for _ in range(int(input())):
	test()


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


T = int(input())
while T > 0:
	T = T - 1
	N = int(input())
	a = input()
	c = a[N - 1]
	if c in a[0:N - 1]:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	size = len(s)
	if s[size - 1] in s[0:size - 1]:
		print('YES')
	else:
		print('NO')
	t = t - 1


for _ in range(int(input())):
	x = int(input())
	lst = list(str(input()))
	if lst.count(lst[x - 1]) > 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	s2 = s[n - 1]
	s3 = set(s[:-1])
	if s2 in s3:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	ch = s[len(s) - 1]
	c = s.count(ch)
	if c > 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	check = False
	g = ''
	for j in s[:len(s) - 1]:
		g = g + j
	for j in s[len(s) - 1]:
		if j in g:
			pass
		else:
			check = True
			break
	if check == True:
		print('NO')
	else:
		print('YES')


for t in range(int(input())):
	N = int(input())
	text = input()
	result = text[:-1].find(text[N - 1])
	if result == -1:
		print('NO')
	else:
		print('YES')


def splitStr(S):
	N = len(S)
	if N % 2 == 0:
		for i in range(1, int(N / 2) + 1):
			if not S[-i:] in S[:-i]:
				return 'NO'
			else:
				return 'YES'
	else:
		for i in range(1, int((N + 1) / 2)):
			if not S[-i:] in S[:-i]:
				return 'NO'
			else:
				return 'YES'
for _ in range(int(input())):
	N = int(input())
	S = input()
	print(splitStr(S))


t = int(input())
for tc in range(t):
	n = int(input())
	s = input()
	x = s[0:n - 1]
	y = s[-1]
	if y in x:
		print('YES')
	else:
		print('NO')


for tc in range(int(input())):
	n = int(input())
	s = input()
	kmap = {}
	for char in s[0:n - 1]:
		if char not in kmap:
			kmap[char] = 1
	if s[-1] not in kmap:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	s = input()
	for j in range(len(s)):
		a = s[:len(s) - 1]
		b = s[-1]
	if b in a:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	n = int(input())
	s = input()
	if s[-1] in s[:-1]:
		print('YES')
	else:
		print('NO')


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


for _ in range(int(input())):
	N = int(input())
	s = input()
	flag = False
	if s[N - 1] in s[:N - 1]:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	t = t - 1
	n = int(input())
	s = input()
	c = s[n - 1]
	if s.count(c) >= 2:
		print('YES')
	else:
		print('NO')


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	string = input()
	a = string[:n - 1]
	b = string[-1]
	if b in a:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = s[:n - 1]
	b = s[-1]
	if b in a:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	a = list(s[:-1])
	b = s[-1]
	if b in a:
		print('YES')
	else:
		print('NO')


x = int(input())
ip = []
for jk in range(0, x):
	lp = int(input())
	dd = str(input())
	ip.append(dd)
for vv in ip:
	hjk = vv[-1]
	opl = vv[0:len(vv) - 1]
	if hjk in opl:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	l = input()
	l = list(l)
	if l.count(l[-1]) > 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	ip = input()
	if ip[-1] in ip[:-1]:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	z = s[-1]
	if z in s[0:len(s) - 1]:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	st = input()
	a = st[:-1]
	b = st[-1]
	if a + b == st and b in a:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = input()
	l = [*l]
	s = l.pop()
	if s in l:
		print('YES')
	else:
		print('NO')


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	f = 0
	for i in range(n - 1):
		if s[i] == s[n - 1]:
			f = 1
			break
	if f == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	found = 0
	last = s[n - 1]
	for i in range(0, n - 1):
		if s[i] == last:
			found = 1
			break
	if found == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	a = s[-1]
	b = s[:-1]
	if a in b:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	x = input()
	if x[-1] in x[:-1]:
		print('YES')
	else:
		print('NO')


t = int(input())
for x in range(t):
	n = int(input())
	s = input()
	check = False
	for j in range(len(s) - 1):
		if s[j] == s[len(s) - 1]:
			check = True
			break
	if check:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	s1 = s[:-1]
	s2 = s[-1]
	if s2 in s1:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	input()
	x = input()
	hailee = lambda s: 'YES' if s[-1] in s[:-1] else 'NO'
	print(hailee(x))


for _ in range(int(input())):
	n = int(input())
	s = input()
	i = len(s) - 1
	if s[-1] in s[:n - 1]:
		print('YES')
	else:
		print('NO')


def SplitIt(s, n):
	if s.count(s[-1]) >= 2:
		return 'YES'
	return 'NO'
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(SplitIt(s, n))


testcases = int(input())
for i in range(testcases):
	n = int(input())
	data = str(input())
	val = data[:n - 1]
	if data[-1] in val:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	c = input()
	if c[n - 1:n] in c[0:n - 1]:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	num = int(input())
	text = input()
	a = text[:num - 1]
	b = text[-1]
	if b in a:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	substr = s[len(s) - 1]
	flag = 0
	for i in range(0, len(s) - 1):
		if s[i] == substr:
			flag = 1
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	x = s[len(s) - 1]
	y = s[:len(s) - 1]
	if x in y:
		print('YES')
	else:
		print('NO')