Shefin gives you a string S and you have to find a non-empty string P such that:  
P is a substring of S.
No non-empty substring of P is a prefix of S.
No non-empty substring of P is a suffix of S.

For all such possible strings, find the length of the longest string satisfying all the conditions. If no such string is possible, print -1. 

A string A is a substring of a string B if A can be obtained from B by deleting several (possibly zero) characters from the beginning and several (possibly zero) characters from the end.  
A prefix of a string A, is a substring of A that occurs at the beginning of A. For example, "code" is a prefix of "codechef", but "ode" is not.  
A suffix of a string A, is a substring of A that occurs at the end of A. For example, "chef" is a suffix of "codechef", but "he" is not.

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

- The first line of the input contains an integer T - denoting number of test cases.
- Each test case contains a string S consisting of lowercase english alphabets only. 

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

For each test case, print a single integer. If a string P exists based on the given conditions, print the maximum length of the possible string. Otherwise, print -1.

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

${1 ≤T ≤10^{4}}$
${1 ≤\lvert S \rvert ≤10^{6}}$
- Sum of ${\lvert S \rvert}$ over all test cases does not exceed $10^{6}$.
$S$ consists of lowercase english alphabets only.

----- Sample Input 1 ------ 
2
abcdab
aaa

----- Sample Output 1 ------ 
2
-1

----- explanation 1 ------ 
Test Case $1$: The maximum length of the string satisfying all required conditions is $2$. The string $\texttt{cd}$ satisfies all the conditions. It can be proven that no string of length greater than $2$ exists which can satisfy all the conditions.  

Test Case $2$: There is no string possible which satisfies all the required conditions. Thus, the answer is $-1$.

Difficulty: MEDIUM
Tags: String algorithms

Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	s = input()
	a = []
	for i in s:
		if i in [s[0], s[-1]]:
			a.append(' ')
		else:
			a.append(i)
	a = ''.join(a)
	a = a.split()
	a = [len(i) for i in a]
	if a == []:
		print(-1)
	else:
		print(max(a))


for _ in range(int(input())):
	s = input()
	(m, cur) = (0, 0)
	b = {s[0], s[-1]}
	for i in s:
		if i not in b:
			cur += 1
		else:
			if cur > m:
				m = cur
			cur = 0
	print(m if m else -1)


for _ in range(int(input())):
	s = input()
	(mxlen, dis) = (0, 0)
	for i in s[1:-1]:
		if i != s[0] and i != s[-1]:
			dis += 1
		else:
			mxlen = max(mxlen, dis)
			dis = 0
	mxlen = max(mxlen, dis)
	print(mxlen if mxlen else -1)


for i in range(int(input())):
	s = input()
	l = []
	map = []
	for j in s:
		map.append(0)
		l.append(j)
	for j in range(len(l)):
		if l[j] == l[0]:
			map[j] = 1
		if l[j] == l[len(s) - 1]:
			map[j] = 2
	a = 0
	count = 0
	c = []
	flag = 0
	for j in range(len(map)):
		if flag == 0 and map[j] == 1:
			flag = 1
			a = 1
		elif flag == 0 and map[j] == 2:
			flag = 1
			a = 2
		elif flag == 1 and map[j] == 0:
			count += 1
		elif flag == 1 and map[j] == 2 and (a == 1):
			c.append(count)
			count = 0
			a = 2
		elif flag == 1 and map[j] == 1 and (a == 2):
			c.append(count)
			count = 0
			a = 1
		elif flag == 1 and map[j] == 2 and (a == 2):
			c.append(count)
			count = 0
			a = 2
		elif flag == 1 and map[j] == 1 and (a == 1):
			c.append(count)
			count = 0
			a = 1
	if len(c) == 0:
		print('-1')
	elif max(c) == 0:
		print('-1')
	else:
		print(max(c))


c = int(input())
t = []
for jk in range(0, c):
	pr = str(input())
	t.append(pr)
for mm in t:
	vb = [mm[0], mm[-1]]
	final = []
	ue = ''
	for thu in range(0, len(mm)):
		if mm[thu] in vb:
			final.append(len(ue))
			ue = ''
			continue
		else:
			ue += mm[thu]
	upr = max(final)
	if upr == 0:
		print(-1)
	else:
		print(upr)


for _ in range(int(input())):
	s = input()
	j = 1
	max1 = 0
	cnt = 0
	while j < len(s):
		if s[j] != s[-1] and s[j] != s[0]:
			cnt += 1
		else:
			if cnt > max1:
				max1 = cnt
			cnt = 0
		j += 1
	if cnt > max1:
		max1 = cnt
	if max1 == 0:
		print(-1)
	else:
		print(max1)


for i in range(int(input())):
	st = input()
	length = len(st)
	first = st[0]
	last = st[length - 1]
	j = 1
	count = 0
	max1 = 0
	while j < length - 1:
		if st[j] != first and st[j] != last:
			count += 1
		else:
			if count > max1:
				max1 = count
			count = 0
		j += 1
	if count > max1:
		max1 = count
	if max1 == 0:
		print(-1)
	else:
		print(max1)


t = int(input())
for i in range(t):
	s = input()
	c = 0
	if len(s) == 1 or len(s) == 2:
		print(-1)
		continue
	a = s[0]
	b = s[len(s) - 1]
	m = 0
	for i in range(1, len(s) - 1):
		if s[i] != a and s[i] != b:
			c = c + 1
			m = max(c, m)
		else:
			c = 0
	if m == 0:
		print(-1)
	else:
		print(m)


for _ in range(int(input())):
	s = input()
	n = len(s)
	p = s[0]
	q = s[-1]
	c = 0
	ans = 0
	for i in range(n):
		if s[i] != p and s[i] != q:
			c += 1
			ans = max(c, ans)
		else:
			c = 0
	if ans:
		print(ans)
	else:
		print(-1)


for _ in range(int(input())):
	s = input()
	(n, ans, count) = (len(s), 0, 0)
	for i in s[1:n - 1]:
		if i != s[0] and i != s[-1]:
			count += 1
		else:
			count = 0
		ans = max(ans, count)
	if ans > 0:
		print(ans)
	else:
		print(-1)


def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

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

def solve(wrd):
	forbidden = [wrd[0], wrd[-1]]
	runningmax = 0
	maxx = 0
	for i in wrd:
		if i == wrd[0] or i == wrd[-1]:
			if runningmax >= maxx:
				maxx = runningmax
			runningmax = 0
		else:
			runningmax += 1
	if maxx == 0:
		return -1
	return maxx

def main():
	for i in range(inp()):
		print(solve(st()))
main()


def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

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

def solver(wrd):
	count = 0
	maxx = 0
	for i in wrd:
		if i == wrd[0] or i == wrd[-1]:
			if count >= maxx:
				maxx = count
			count = 0
		else:
			count += 1
	if maxx == 0:
		maxx -= 1
	return maxx
for i in range(inp()):
	print(solver(st()))


def solver(wrd):
	count = 0
	maxx = 0
	for i in wrd:
		if i != wrd[0] and i != wrd[-1]:
			count += 1
		else:
			if count >= maxx:
				maxx = count
			count = 0
	if maxx == 0:
		maxx -= 1
	return maxx
for i in range(int(input())):
	print(solver(input()))


t = int(input())
while t:
	s = input()
	ans = ''
	mx = -1
	(l, r) = (s[0], s[-1])
	for i in range(1, len(s) - 1):
		if s[i] != l and s[i] != r:
			f = True
		else:
			f = False
		if f:
			ans += s[i]
		else:
			mx = max(len(ans), mx)
			ans = ''
	mx = max(len(ans), mx)
	if mx == 0:
		mx = -1
	print(mx)
	t -= 1


for _ in range(int(input())):
	s = input()
	s = s.replace(s[0], ' ').replace(s[-1], ' ')
	s = s.split()
	if s == []:
		print(-1)
		continue
	print(len(sorted(s, key=len)[-1]))


for i in range(int(input())):
	st = input()
	le = len(st)
	temp = 0
	ans = 0
	for j in range(1, le - 1):
		if st[j] != st[0] and st[j] != st[-1]:
			temp += 1
		else:
			ans = max(temp, ans)
			temp = 0
	ans = max(temp, ans)
	if ans == 0:
		print(-1)
		continue
	print(ans)


for i in range(int(input())):
	s = input()
	a = s[0]
	b = s[-1]
	c1 = 0
	c2 = 0
	for i in s:
		if i == a or i == b:
			if c1 < c2:
				c1 = c2
			c2 = 0
		else:
			c2 += 1
	print(c1 if c1 else -1)


for _ in range(int(input())):
	s = input()
	c = 0
	m = 0
	f = s[0]
	l = s[-1]
	for i in s:
		if i == f or i == l:
			m = max(m, c)
			c = 0
		else:
			c += 1
	if m == 0:
		print(-1)
	else:
		print(m)


def solve(s):
	n = len(s)
	res = ''
	fir = s[0]
	last = s[-1]
	for i in range(1, n - 1):
		if s[i] == fir or s[i] == last:
			res += '0'
		else:
			res += '1'
	cnt = 0
	curr = 0
	for i in range(len(res)):
		if res[i] == '1':
			curr += 1
		else:
			curr = 0
		cnt = max(curr, cnt)
	if cnt == 0:
		return -1
	else:
		return cnt
for _ in range(int(input())):
	s = input()
	print(solve(s))


tst = int(input())
for i in range(tst):
	st = input()
	s = ''
	c = []
	e = 0
	for j in range(len(st)):
		if st[j] == st[0] or st[j] == st[-1]:
			s = s + '0'
		else:
			s = s + '1'
	for j in range(len(st)):
		if s[j] == '1':
			e = e + 1
		else:
			c.append(e)
			e = 0
	ans = max(c)
	if ans > 0:
		print(ans)
	else:
		print('-1')


t = int(input())
for i in range(t):
	s1 = input()
	n = len(s1)
	c = 0
	ans = 0
	for j in range(n):
		if s1[0] == s1[j] or s1[j] == s1[n - 1]:
			if ans < c:
				ans = c
			c = 0
		else:
			c += 1
	print(-1 if ans == 0 else ans)


for _ in range(int(input())):
	s1 = input()
	n = len(s1)
	count = max_count = 0
	for i in range(n):
		if s1[0] == s1[i] or s1[i] == s1[n - 1]:
			if max_count < count:
				max_count = count
			count = 0
		else:
			count += 1
	if max_count == 0:
		print(-1)
	else:
		print(max_count)


for i in range(0, int(input())):
	a = input()
	start = a[0]
	end = a[-1]
	a = a.replace(start, ' ')
	a = str(a).replace(end, ' ')
	a = a.split()
	maxm = -1
	for k in a:
		lenn = len(k)
		if maxm < lenn:
			maxm = lenn
	print(maxm)


for _ in range(int(input())):
	s = input()
	cnt = 0
	max_ = -1
	for i in range(1, len(s) - 1):
		if s[i] != s[0] and s[i] != s[-1]:
			cnt += 1
			if cnt > max_:
				max_ = cnt
		else:
			cnt = 0
	print(max_)


t = int(input())
for i in range(t):
	max_l = 0
	s = input()
	if len(s) == 1 or len(s) == 2:
		print(-1)
		continue
	else:
		c = 0
		for i in range(1, len(s) - 1):
			if s[i] != s[0] and s[i] != s[len(s) - 1]:
				c += 1
				if max_l < c:
					max_l = c
			else:
				c = 0
	if max_l == 0:
		print(-1)
	else:
		print(max_l)


T = int(input())
for x in range(T):
	s = input()
	c = 0
	a = 0
	for i in s:
		if i != s[0] and i != s[-1]:
			c += 1
		else:
			a = max(c, a)
			c = 0
	if a == 0:
		print(-1)
	else:
		print(a)


T = int(input())
for i in range(T):
	s = input()
	count = 0
	ans = 0
	for i in s:
		if i != s[0] and i != s[-1]:
			count += 1
		else:
			ans = max(count, ans)
			count = 0
	if ans == 0:
		print('-1')
	else:
		print(ans)


tests = int(input())
for i in range(tests):
	string = input()
	ans = 0
	temp = 0
	for j in string:
		if j != string[0] and j != string[-1]:
			temp += 1
		else:
			ans = max(ans, temp)
			temp = 0
	if ans == 0:
		ans = -1
	print(ans)


for i in range(int(input())):
	s = input()
	n = len(s)
	count = 0
	length = 0
	for i in range(n):
		if s[i] != s[0] and s[i] != s[-1]:
			count += 1
			if count > length:
				length += 1
		else:
			count = 0
	if length == 0:
		print(-1)
	else:
		print(length)


for _ in range(int(input())):
	s = input()
	c = 0
	m = 0
	for i in range(len(s)):
		if s[i] != s[0] and s[i] != s[-1]:
			c += 1
			if c > m:
				m += 1
		else:
			c = 0
	if m == 0:
		print(-1)
	else:
		print(m)


def string(s, n):
	start = s[0]
	end = s[-1]
	m = 0
	count = 0
	for i in range(1, n - 1):
		if s[i] != end and s[i] != start:
			count += 1
			if count > m:
				m = count
		else:
			count = 0
	if m == 0:
		return -1
	else:
		return m
for _ in range(int(input())):
	s = input()
	n = len(s)
	print(string(s, n))


for _ in range(int(input())):
	s = input()
	n = len(s)
	c = m = 0
	for i in range(n):
		if s[0] == s[i] or s[i] == s[n - 1]:
			if m < c:
				m = c
			c = 0
		else:
			c += 1
	if m == 0:
		print(-1)
	else:
		print(m)


for _ in range(int(input())):
	s = input()
	f = s[0]
	l = s[-1]
	mx = 0
	count = 0
	for a in s:
		if a == f or a == l:
			if count > mx:
				mx = count
			count = 0
		else:
			count += 1
	print(-1) if mx == 0 else print(mx)


a = int(input())
while a != 0:
	b = input()
	c = b.replace(b[len(b) - 1], b[0])
	c = c.split(b[0])
	l = []
	for str1 in c:
		len1 = len(str1)
		l.append(len1)
	if max(l) == 0:
		print(-1)
	else:
		print(max(l))
	a = a - 1


for u in range(int(input())):
	s = input()
	pns = ''
	ns = ''
	for v in range(1, len(s)):
		if s[v] != s[0] and s[v] != s[len(s) - 1]:
			ns += s[v]
		else:
			if len(ns) > len(pns):
				pns = ns
			ns = ''
	if len(pns) > 0:
		print(len(pns))
	else:
		print(-1)


for _ in range(int(input())):
	s = input()
	c = -1
	t = -1
	for i in range(len(s)):
		if s[i] != s[0] and s[i] != s[len(s) - 1]:
			if t < 0:
				t = 0
			t += 1
		else:
			c = max(t, c)
			t = -1
	print(c)


for i in range(int(input())):
	x = input()
	t = 0
	s = 0
	for i in range(1, len(x)):
		if x[i] == x[0] or x[i] == x[-1]:
			if t > s:
				s = t
			t = 0
		else:
			t = t + 1
	if s == 0:
		print('-1')
	else:
		print(s)


for i in range(int(input())):
	s = input()
	n = len(s)
	i = 0
	count = n
	l = [s[0], s[-1]]
	count = 0
	i = 0
	j = 1
	if n <= 2:
		print(-1)
		continue
	while j < n:
		if s[j] not in l:
			i += 1
		else:
			if i > count:
				count = i
			i = 0
		j += 1
	if count > 0:
		print(count)
	else:
		print(-1)


t = int(input())
for j in range(t):
	s = input()
	m = 0
	count = 0
	for i in range(1, len(s) - 1):
		if s[i] != s[0] and s[i] != s[-1]:
			count += 1
			m = max(count, m)
		else:
			count = 0
	if m == 0:
		print(-1)
	else:
		print(m)


for _ in range(int(input())):
	string = input()
	first = string[0]
	last = string[-1]
	string = string.replace(first, '_')
	string = string.replace(last, '_')
	lst = list(string.split('_'))
	maxlen = -1
	if len(lst) != 0:
		for i in lst:
			k = len(i)
			if k > maxlen and k:
				maxlen = k
	print(maxlen)


t = int(input())
for i in range(t):
	result = []
	string = str(input())
	first = string[0]
	last = string[len(string) - 1]
	max_length = 0
	cnt = 0
	for j in range(1, len(string) - 1):
		if string[j] != first and string[j] != last:
			cnt += 1
		else:
			cnt = 0
		max_length = max(max_length, cnt)
	if max_length == 0:
		print(-1)
	else:
		print(max_length)


t = int(input())
for _ in range(t):
	st = input()
	l = len(st)
	c = 0
	ans = 0
	for i in range(l):
		if st[i] != st[0] and st[i] != st[l - 1]:
			c = c + 1
		else:
			c = 0
		ans = max(ans, c)
	if ans == 0:
		print(-1)
	else:
		print(ans)


def solve(string):
	num = len(string)
	prefix = string[0]
	suffix = string[num - 1]
	ref = []
	count = 0
	for i in range(0, num):
		if string[i] == prefix or string[i] == suffix:
			ref.append(count)
			count = 0
		else:
			count += 1
	temp1 = max(ref)
	if temp1 == 0:
		return -1
	else:
		return temp1
n = int(input())
while n:
	string = input()
	print(solve(string))
	n -= 1


t = int(input())
for i in range(0, t):
	s = input()
	c = [i for i in s]
	for i in range(0, len(c)):
		if c[i] == s[0] or c[i] == s[len(s) - 1]:
			c[i] = '0'
	count = 0
	a = []
	for i in range(len(c)):
		if c[i] != '0':
			count = count + 1
		else:
			a.append(count)
			count = 0
	if max(a) == 0:
		print('-1')
	else:
		print(max(a))


for t in range(int(input())):
	s = input()
	bin_s = ''
	for x in range(len(s)):
		if s[x] in [s[0], s[-1]]:
			bin_s += '0'
		else:
			bin_s += '1'
	(ans, temp) = (0, 0)
	for y in range(len(bin_s)):
		if bin_s[y] == '1':
			temp += 1
		else:
			temp = 0
		ans = max(ans, temp)
	print(ans if ans > 0 else -1)


t = int(input())
for i in range(t):
	s = str(input())
	v = []
	c = 0
	if len(s) <= 2:
		print(-1)
	else:
		for i in s[1:-1]:
			if i != s[0] and i != s[-1]:
				c += 1
			else:
				v.append(c)
				c = 0
		v.append(c)
		if max(v) != 0:
			print(max(v))
		else:
			print(-1)


def len_check(st):
	e = [st[0], st[-1]]
	st = st.replace(e[0], '0')
	st = st.replace(e[1], '0')
	m_c = 0
	cnt = 0
	last = 0
	for (i, j) in enumerate(st):
		if j == '0':
			last = i
			continue
		cnt = max(cnt, i - last)
	if cnt == 0:
		return -1
	else:
		return cnt
T = int(input())
for i in range(T):
	a = input()
	print(len_check(a))


t = int(input())
for j in range(t):
	arr = input()
	max = -1
	new_arrays = arr.split(arr[0])
	for (i, element) in enumerate(new_arrays):
		new_arrays[i] = element.split(arr[-1])
		for item in new_arrays[i]:
			if len(item) > max and len(item) > 0:
				max = len(item)
	print(max)


for _ in range(int(input())):
	S = input()
	print(max([len(k) for k in S.replace(S[0], ' ').replace(S[-1], ' ').split()], default=0) or -1)


for _ in range(int(input())):
	a = input()
	l1 = []
	p = a[0]
	s = a[-1]
	count = 0
	for i in a:
		if i == p or i == s:
			l1.append(count)
			count = 0
		else:
			count += 1
	len = max(l1)
	if len != 0:
		print(len)
	else:
		print(-1)


for _ in range(int(input())):
	a = input()
	a = a.replace(a[0], ' ')
	a = a.replace(a[-1], ' ')
	l = a.split()
	lenmax = 0
	for i in l:
		j = len(i)
		if j > lenmax:
			lenmax = j
	if lenmax != 0:
		print(lenmax)
	else:
		print(-1)


T = int(input())
for i in range(0, T):
	a = input()
	l = a[0]
	r = a[-1]
	bb = set(a)
	if len(bb) == 1:
		print(-1)
	elif len(bb) == 2 and l != r:
		print(-1)
	else:
		a = a.split(l)
		ans = 0
		for j in a:
			c = j.split(r)
			for k in c:
				ans = max(ans, len(k))
		if ans == 0:
			print(-1)
		else:
			print(ans)


for _ in range(int(input())):
	a = input()
	q = []
	p = a[0]
	s = a[-1]
	c = 0
	for i in a:
		if i == p or i == s:
			q.append(c)
			c = 0
		else:
			c += 1
	g = max(q)
	if g == 0:
		print(-1)
	else:
		print(g)