Ashish has a string $s$ of length $n$ containing only characters 'a', 'b' and 'c'.

He wants to find the length of the smallest substring, which satisfies the following conditions:

Length of the substring is at least $2$

'a' occurs strictly more times in this substring than 'b'

'a' occurs strictly more times in this substring than 'c'

Ashish is busy planning his next Codeforces round. Help him solve the problem.

A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.


-----Input-----

The first line contains a single integer $t$ $(1 \le t \le 10^{5})$  — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ $(2 \le n \le 10^{6})$  — the length of the string $s$.

The second line of each test case contains a string $s$ consisting only of characters 'a', 'b' and 'c'.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^{6}$.


-----Output-----

For each test case, output the length of the smallest substring which satisfies the given conditions or print $-1$ if there is no such substring.


-----Examples-----

Input
3
2
aa
5
cbabb
8
cacabccc
Output
2
-1
3


-----Note-----

Consider the first test case. In the substring "aa", 'a' occurs twice, while 'b' and 'c' occur zero times. Since 'a' occurs strictly more times than 'b' and 'c', the substring "aa" satisfies the condition and the answer is $2$. The substring "a" also satisfies this condition, however its length is not at least $2$.

In the second test case, it can be shown that in none of the substrings of "cbabb" does 'a' occur strictly more times than 'b' and 'c' each.

In the third test case, "cacabccc", the length of the smallest substring that satisfies the conditions is $3$.

Difficulty: MEDIUM
Tags: String algorithms

Complete search

Implementation

Greedy algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
import sys
ans = []
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	s = sys.stdin.readline().strip()
	if s.find('aa') > -1:
		ans.append('2')
	elif s.find('aca') > -1 or s.find('aba') > -1:
		ans.append('3')
	elif s.find('abca') > -1 or s.find('acba') > -1:
		ans.append('4')
	elif s.find('abbacca') > -1 or s.find('accabba') > -1:
		ans.append('7')
	else:
		ans.append('-1')
print('\n'.join(ans))


for s in [*open(0)][2::2]:
	a = -1
	for i in ('abbacca', 'accabba', 'acba', 'abca', 'aca', 'aba', 'aa'):
		if i in s:
			a = len(i)
	print(a)


pairs = ['aa', 'aba', 'aca', 'abca', 'acba', 'accabba', 'abbacca']
for s in [*open(0)][2::2]:
	for i in pairs:
		if i in s:
			print(len(i))
			break
	else:
		print(-1)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(sys.stdin.readline())
	s = sys.stdin.readline().rstrip()
	if 'aa' in s:
		print(2)
	elif 'aba' in s:
		print(3)
	elif 'aca' in s:
		print(3)
	elif 'abca' in s:
		print(4)
	elif 'acba' in s:
		print(4)
	elif 'abbacca' in s:
		print(7)
	elif 'accabba' in s:
		print(7)
	else:
		print(-1)


import sys
input = sys.stdin.readline

def printL(list):
	sys.stdout.write(' '.join(map(str, list)) + '\n')

def printN(n):
	sys.stdout.write(str(n) + '\n')
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	b = False
	for i in ('aa', 'aba', 'aca', 'abca', 'acba', 'accabba', 'abbacca'):
		if i in s:
			printN(len(i))
			b = True
			break
	if not b:
		printN(-1)


import sys
import bisect
import math
input = lambda : sys.stdin.readline().strip()
mod = 10 ** 9 + 9

def solve():
	n = int(input())
	s = input()
	if 'aa' in s:
		return 2
	elif 'aca' in s or 'aba' in s:
		return 3
	elif 'abca' in s or 'acba' in s:
		return 4
	elif 'abbacca' in s or 'accabba' in s:
		return 7
	else:
		return -1
t = 1
t = int(input())
for _ in range(t):
	print(solve())


import sys
input = sys.stdin.readline
for _ in range(int(input().strip())):
	n = int(input().strip())
	s = input().strip()
	if 'aa' in s:
		print(2)
	elif 'aba' in s or 'aca' in s:
		print(3)
	elif 'abca' in s or 'acba' in s:
		print(4)
	elif 'abbacca' in s or 'accabba' in s:
		print(7)
	else:
		print(-1)


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
sys.setrecursionlimit(10000000)
for _ in range(I()):
	n = I()
	s = S()
	if 'aa' in s:
		print(2)
		continue
	if 'aba' in s or 'aca' in s:
		print(3)
		continue
	if 'abca' in s or 'acba' in s:
		print(4)
		continue
	if 'abbacca' in s or 'accabba' in s:
		print(7)
		continue
	print(-1)


l = {'aa': 2, 'aba': 3, 'aca': 3, 'abca': 4, 'acba': 4, 'abbacca': 7, 'accabba': 7}
import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	s = sys.stdin.readline()
	for x in l:
		if x in s:
			print(l[x])
			break
	else:
		print(-1)


t = int(input())
ret = []
for i in range(t):
	n = int(input())
	s = input()
	if 'aa' in s:
		ret.append(2)
	elif 'aca' in s or 'aba' in s:
		ret.append(3)
	elif 'abca' in s or 'acba' in s:
		ret.append(4)
	elif 'abbacca' in s or 'accabba' in s:
		ret.append(7)
	else:
		ret.append(-1)
print(*ret, sep='\n')


def solve():
	input()
	s = input().strip()
	if 'aa' in s:
		return print(2)
	elif 'aba' in s or 'aca' in s:
		return print(3)
	elif 'abca' in s or 'acba' in s:
		print(4)
	elif 'abbacca' in s or 'accabba' in s:
		print(7)
	else:
		print(-1)
n = int(input())
for i in range(n):
	solve()


from sys import stdin, stdout
import sys
import math
import itertools
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)
import re

def main():
	t = int(stdin.readline().strip())
	for j in range(1, t + 1):
		n = int(stdin.readline().strip())
		s = stdin.readline().strip()
		if re.search('aa', s):
			print(2)
		elif re.search('aba', s) or re.search('aca', s):
			print(3)
		elif re.search('abca', s) or re.search('acba', s):
			print(4)
		elif re.search('abbacca', s) or re.search('accabba', s):
			print(7)
		else:
			print(-1)
main()


for _ in range(int(input())):
	n = int(input())
	s = input()
	if 'aa' in s:
		print(2)
	elif 'aca' in s or 'aba' in s:
		print(3)
	elif 'abca' in s or 'acba' in s:
		print(4)
	elif 'abbacca' in s or 'accabba' in s:
		print(7)
	else:
		print(-1)


def solution(S):
	if 'aa' in S:
		return 2
	if 'aba' in S or 'aca' in S:
		return 3
	if 'abca' in S or 'acba' in S:
		return 4
	if 'abbacca' in S or 'accabba' in S:
		return 7
	return -1
t = int(input())
for _ in range(t):
	n = input()
	s = input()
	print(solution(s))


t = int(input())
for i in range(t):
	l = input()
	s = input()
	if 'aa' in s:
		print(2)
	elif 'aba' in s:
		print(3)
	elif 'aca' in s:
		print(3)
	elif 'abca' in s:
		print(4)
	elif 'acba' in s:
		print(4)
	elif 'accabba' in s:
		print(7)
	elif 'abbacca' in s:
		print(7)
	else:
		print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	y = 0
	le = 0
	if 'aa' in s:
		y = 1
		le = 2
	elif 'aba' in s:
		y = 1
		le = 3
	elif 'aca' in s:
		y = 1
		le = 3
	elif 'abca' in s:
		y = 1
		le = 4
	elif 'acba' in s:
		y = 1
		le = 4
	elif 'abbacca' in s:
		y = 1
		le = 7
	elif 'accabba' in s:
		y = 1
		le = 7
	if y == 1:
		print(le)
	else:
		print(-1)


from collections import defaultdict

def fun(n, s):
	if 'aa' in s:
		return 2
	elif 'aba' in s:
		return 3
	elif 'aca' in s:
		return 3
	elif 'abca' in s:
		return 4
	elif 'acba' in s:
		return 4
	elif 'abbacca' in s:
		return 7
	elif 'accabba' in s:
		return 7
	else:
		return -1
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	print(fun(n, s))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input().rstrip()
	p = q = -1
	for i in range(n):
		if s[i] == 'a' and p == -1:
			p = i
		elif s[i] == 'a' and p != -1:
			q = i
	if q == -1:
		print(-1)
		continue
	s = s[p:q + 1]
	k = []
	t = ''
	for i in s:
		t += i
		if i == 'a' and len(t) != 1:
			k += [t]
			t = i
	k.sort(key=lambda x: len(x))
	flag = 0
	for i in k:
		if flag:
			break
		if i == 'aa':
			print(2)
			flag = 1
		elif i in ['aba', 'aca']:
			print(3)
			flag = 1
		elif i in ['abca', 'acba']:
			print(4)
			flag = 1
	if flag:
		continue
	if 'abbacca' in s or 'accabba' in s:
		print(7)
	else:
		print(-1)


secs = ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba']
for _ in range(int(input())):
	input()
	string = input()
	ended = False
	for j in secs:
		if j in string:
			print(len(j))
			ended = True
			break
	if not ended:
		print(-1)


nums = eval(input())
for i in range(nums):
	n = input()
	abc = input()
	if 'aa' in abc:
		print(2)
	elif 'aba' in abc or 'aca' in abc:
		print(3)
	elif 'abca' in abc or 'acba' in abc:
		print(4)
	elif 'abbacca' in abc or 'accabba' in abc:
		print(7)
	else:
		print(-1)


t = int(input())
for p in range(t):
	n = int(input())
	s = input()
	ans = 0
	if 'aa' in s:
		ans = 2
	elif 'aba' in s:
		ans = 3
	elif 'aca' in s:
		ans = 3
	elif 'abca' in s:
		ans = 4
	elif 'acba' in s:
		ans = 4
	elif 'abbacca' in s:
		ans = 7
	elif 'accabba' in s:
		ans = 7
	if ans == 0:
		print('-1')
	else:
		print(ans)


n = int(input())
for i in range(0, n):
	size = int(input())
	string = input()
	if 'aa' in string:
		print(2)
	elif 'aba' in string:
		print(3)
	elif 'aca' in string:
		print(3)
	elif 'acba' in string:
		print(4)
	elif 'abca' in string:
		print(4)
	elif 'abbacca' in string:
		print(7)
	elif 'accabba' in string:
		print(7)
	else:
		print(-1)


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
chk = ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba']
for _ in range(int(input())):
	n = int(input())
	s = input()
	for i in chk:
		if i in s:
			print(len(i))
			break
	else:
		print(-1)


t = int(input())
for q in range(t):
	n = int(input())
	s = input()
	if 'aa' in s:
		print(2)
	elif 'aba' in s or 'aca' in s:
		print(3)
	elif 'abca' in s or 'acba' in s:
		print(4)
	elif 'abcabca' in s or 'acbacba' in s or 'abbacca' in s or ('abcacba' in s) or ('acbabc' in s) or ('accabba' in s):
		print(7)
	else:
		print(-1)


def main():
	input()
	string = input()
	for st in ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba']:
		if st in string:
			return len(st)
	return -1
tests = int(input())
while tests:
	tests -= 1
	print(main())


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	sys.stderr = open('error.txt', 'w')
depth = 1000000
mod = 1000000007
lim = mod * mod
sys.setrecursionlimit(depth)
linp = lambda : list(minp())
minp = lambda : map(int, input().split())
from math import inf, ceil, sqrt, log2, gcd
from collections import defaultdict, deque
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
dp = ['aa', 'aba', 'aca', 'acba', 'abca', 'accabba', 'abbacca']

def solve():
	(n, s) = (input(), input())
	for e in dp:
		if e in s:
			return len(e)
	return -1
for _ in range(int(input())):
	print(solve())


pairs = ['aa', 'aba', 'aca', 'abca', 'acba', 'accabba', 'abbacca']
for _ in range(int(input())):
	n = int(input())
	s = input()
	for i in pairs:
		if i in s:
			print(len(i))
			break
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = -1
	pos = ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba']
	for i in pos:
		if i in s:
			a = len(i)
			break
	print(a)


for test in range(int(input())):
	n = int(input())
	s = input()
	bool = True
	for i in ('aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba'):
		if i in s:
			print(len(i))
			bool = False
			break
	if bool:
		print(-1)


def solve():
	_ = int(input())
	s = input()
	words = ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba']
	for word in words:
		if word in s:
			print(len(word))
			return
	print(-1)
for _ in range(int(input())):
	solve()


d = ['aa', 'aca', 'aba', 'acba', 'abca', 'accabba', 'abbacca']
t = int(input())
for j in range(t):
	n = int(input())
	a = input()
	ot = -1
	for i in d:
		if i in a:
			ot = len(i)
			break
	print(ot)


from operator import indexOf

def solve(n, string):
	test = ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba']
	ans = -1
	for i in test:
		if i in string:
			ans = len(i)
			break
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	string = input()
	print(solve(n, string))


L = ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba']
for t in range(int(input())):
	n = int(input())
	s = input()
	ans = -1
	for i in L:
		if i in s:
			ans = len(i)
			break
	print(ans)


for i in range(int(input())):
	num = int(input())
	w = input()
	for i in ('aa', 'aba', 'aca', 'abca', 'acba', 'accabba', 'abbacca'):
		if i in w:
			print(i.__len__())
			break
	else:
		print(-1)


from itertools import groupby
for _ in range(int(input())):
	n = int(input())
	s = input()
	z = False
	for i in ['aa', 'aba', 'aca', 'abca', 'acba', 'accabba', 'abbacca']:
		if i in s:
			print(len(i))
			z = True
			break
	if z == False:
		print(-1)


for i in range(int(input())):
	length = int(input())
	string = input()
	master_list = ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba']
	ans_list = [i for i in master_list if i in string]
	if len(ans_list) == 0:
		print(-1)
	else:
		ans_list.sort(key=len)
		print(len(ans_list[0]))


import sys
fastinput = sys.stdin.readline
maybe = ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba']
for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = -1
	for m in maybe:
		if m in s:
			ans = len(m)
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba']
	test = 0
	for i in l:
		if i in s:
			test = 1
			print(len(i))
			break
	if not test:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	MATCH = False
	best = ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba']
	for word in best:
		if word in s:
			print(len(word))
			MATCH = True
			break
	if not MATCH:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	possible = ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba']
	ans = -1
	for i in possible:
		if i in s:
			ans = len(i)
			break
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	b = False
	allowed = ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba']
	for i in allowed:
		if i in s:
			print(len(i))
			b = True
			break
	if not b:
		print(-1)


from math import comb

def f(s):
	if s.find('aa') != -1:
		return 2
	if s.find('aba') != -1:
		return 3
	if s.find('aca') != -1:
		return 3
	if s.find('abca') != -1:
		return 4
	if s.find('acba') != -1:
		return 4
	if s.find('abbacca') != -1:
		return 7
	if s.find('accabba') != -1:
		return 7
	return -1
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	print(f(s))


def solve(n, s):
	if s.find('aa') != -1:
		return 2
	elif s.find('aca') != -1 or s.find('aba') != -1:
		return 3
	elif s.find('abca') != -1 or s.find('acba') != -1:
		return 4
	elif s.find('abbacca') != -1 or s.find('accabba') != -1:
		return 7
	else:
		return -1
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	print(solve(n, s))


import sys
input = sys.stdin.readline

def solve(n, S):
	if 'aa' in S:
		print(2)
	else:
		ans = float('inf')
		for i in range(1, n - 1):
			if S[i - 1] == S[i + 1] == 'a':
				ans = min(ans, 3)
			elif i < n - 2 and S[i - 1] == S[i + 2] == 'a' and (S[i] != S[i + 1]):
				ans = min(ans, 4)
			elif 2 < i < n - 3 and S[i] == 'a' and (S[i - 1] != S[i + 1]) and (S[i - 3] == S[i + 3] == 'a'):
				ans = min(ans, 7)
		print(ans) if ans < float('inf') else print(-1)
for _ in range(int(input())):
	n = int(input())
	S = input().strip()
	solve(n, S)


import sys
for _ in range(int(input())):
	n = int(input())
	s = input()
	if s.find('aa') != -1:
		print(2)
		continue
	if s.find('aba') != -1 or s.find('aca') != -1:
		print(3)
		continue
	if s.find('abca') != -1 or s.find('acba') != -1:
		print(4)
		continue
	if s.find('abbacca') != -1 or s.find('accabba') != -1:
		print(7)
		continue
	print(-1)


for _ in range(int(input())):
	lsen = input()
	st2 = str(input())
	if st2.find('aa') != -1:
		print(2)
	elif st2.find('aca') != -1 or st2.find('aba') != -1:
		print(3)
	elif st2.find('acba') != -1 or st2.find('abca') != -1:
		print(4)
	elif st2.find('accabba') != -1 or st2.find('abbacca') != -1:
		print(7)
	else:
		print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	st = input()
	if st.find('aa') != -1:
		print(2)
	elif st.find('aba') != -1 or st.find('aca') != -1:
		print(3)
	elif st.find('abca') != -1 or st.find('acba') != -1:
		print(4)
	elif st.find('abbacca') != -1 or st.find('accabba') != -1:
		print(7)
	else:
		print(-1)


t = int(input())
a = ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba']
while t:
	t -= 1
	n = int(input())
	s = input().strip()
	ok = False
	for x in a:
		if x in s:
			print(len(x))
			ok = True
			break
	if not ok:
		print('-1\n')


(t, S) = (int(input()), ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba'])
while t != 0:
	(n, T, flag, ans) = (input(), input(), False, 100000000)
	for s in S:
		if s in T:
			flag = True
			ans = ans if ans < len(s) else len(s)
	print(-1 if flag == False else ans)
	t = t - 1


strs = ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba']
t = int(input())
for p in range(t):
	(l, s) = (int(input()), input())
	print(min([len(i) for i in strs if i in s], default=-1))


n_test = int(input())
ee = ['aa', 'aba', 'aca', 'abca', 'acba', 'abbacca', 'accabba']

def solve(s):
	for e in ee:
		if s.count(e) > 0:
			print(len(e))
			return
	print(-1)
for t in range(n_test):
	n = int(input())
	s = input()
	solve(s)


t = int(input())
for _ in range(t):
	n = int(input())
	string = input()
	if string.find('aa') != -1:
		print(2)
	elif string.find('aca') != -1:
		print(3)
	elif string.find('aba') != -1:
		print(3)
	elif string.find('abca') != -1:
		print(4)
	elif string.find('acba') != -1:
		print(4)
	elif string.find('accabba') != -1:
		print(7)
	elif string.find('abbacca') != -1:
		print(7)
	else:
		print(-1)


t = int(input())
i = 0
while i < t:
	n = int(input())
	st = input()
	if st.count('aa') != 0:
		print(2)
	elif st.count('aba') != 0 or st.count('aca') != 0:
		print(3)
	elif st.count('abca') != 0 or st.count('acba') != 0:
		print(4)
	elif st.count('abbacca') != 0 or st.count('accabba') != 0:
		print(7)
	else:
		print(-1)
	i += 1