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

Chef has always been fond of girls, but he could not make any girl his friend. In order to finally make one, he was asked to solve the following problem:

You are given a string $S$ with length $N$. Choose an integer $K$ and two non-empty subsequences $A$ and $B$ of characters of this string, each with length $K$, such that:
$A = B$, i.e. for each valid $i$, the $i$-th character in $A$ is the same as the $i$-th character in $B$.
Let's denote the indices of characters used to construct $A$ by $a_{1}, a_{2}, \ldots, a_{K}$, i.e. $A = (S_{a_{1}}, S_{a_{2}}, \ldots, S_{a_{K}})$. Similarly, let's denote the indices of characters used to construct $B$ by $b_{1}, b_{2}, \ldots, b_{K}$.
If we denote the number of common indices in the sequences $a$ and $b$ by $M$, then $M+1 ≤ K$.

Since Chef is busy right now, he asks you to find the maximum value of $K$ such that it is possible to find sequences $A$ and $B$ which satisfy the given conditions or determine that there is no such $K$.

------  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$ with length $N$.

------  Output ------
For each test case, print a single line containing one integer ― the maximum $K$, or $0$ if there is no solution.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$S$ contains only lowercase English letters

------  Subtasks ------
Subtask #1 (20 points): $N ≤ 8$

Subtask #2 (80 points): original constraints

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

4

anxa
----- Sample Output 1 ------ 
1

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures


Solutions:
for _ in range(int(input())):
	covered = {}
	n = int(input())
	s = input()
	difference = float('inf')
	for i in range(n - 1, -1, -1):
		if s[i] in covered:
			difference = min(difference, covered[s[i]] - i)
		covered[s[i]] = i
	if difference == float('inf'):
		print(0)
		continue
	print(n - difference)


def snek(s, n):
	d = {}
	d1 = float('INF')
	for i in range(n):
		d2 = s[i]
		if d2 in d:
			d1 = min(d1, i - d[d2] + 1)
		d[d2] = i
	return max(0, n - d1 + 1)
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	print(snek(s, n))


def solve(s, n):
	d = {}
	dis = float('INF')
	for i in range(n):
		ch = s[i]
		if ch in d:
			dis = min(dis, i - d[ch] + 1)
		d[ch] = i
	return max(0, n - dis + 1)
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(solve(s, n))


try:
	t = int(input())
except:
	quit()
for _ in range(t):
	n = int(input())
	s = input()
	reps = {}
	m = n
	for i in range(n):
		if s[i] in reps:
			x = i - reps[s[i]] - 1
			reps[s[i]] = i
			m = min(x, m)
		else:
			reps[s[i]] = i
	if m == n:
		print(0)
	else:
		print(n - 1 - m)


import sys

def main():
	t = int(input())
	while t > 0:
		n = int(input())
		st = input()
		min_ch = sys.maxsize
		lastoccur = [-1] * 26
		for i in range(n):
			ele = ord(st[i]) - 97
			if lastoccur[ele] == -1:
				lastoccur[ele] = i
			else:
				val = i - lastoccur[ele] - 1
				lastoccur[ele] = i
				if min_ch > val:
					min_ch = val
		if min_ch == sys.maxsize:
			print(0)
		else:
			print(n - 1 - min_ch)
		t = t - 1
main()


n = int(input())
for x in range(n):
	a = int(input())
	str = input()
	dic = {}
	l = []
	for i in range(a):
		if str[i] in dic:
			z = i - dic[str[i]]
			dic[str[i]] = i
			l.append(z)
		else:
			dic[str[i]] = i
	if len(l) == 0:
		print('0')
	else:
		print(a - min(l))


T = int(input())
for i in range(T):
	n = int(input())
	s = input()
	dic = {}
	l = []
	for i in range(n):
		if s[i] in dic:
			m = i - dic[s[i]]
			dic[s[i]] = i
			l.append(m)
		else:
			dic[s[i]] = i
	if len(l) == 0:
		print(0)
	else:
		print(n - min(l))


import sys

def main():
	t = int(input())
	while t != 0:
		n = int(input())
		st = list(input())
		min_val = sys.maxsize
		last = {}
		for i in range(n):
			if st[i] in last:
				number_ele = i - last[st[i]] - 1
				min_val = min(number_ele, min_val)
				last[st[i]] = i
			else:
				last[st[i]] = i
		if min_val == sys.maxsize:
			print(0)
		else:
			print(n - min_val - 1)
		t -= 1
main()


test_case = int(input())
for test in range(test_case):
	n = int(input())
	A = input()
	idx = {}
	ans = {}
	least = n
	for i in range(n):
		c = idx.get(A[i])
		if c is None:
			idx[A[i]] = i
			ans[A[i]] = n
		else:
			a = ans.get(A[i])
			b = i - c
			idx[A[i]] = i
			if b < a:
				if b < least:
					least = b
				ans[A[i]] = b
	print(n - least)


import sys

def selection(S):
	min = sys.maxsize
	lastoccur = [-1] * 26
	for i in range(n):
		ele = ord(S[i]) - 97
		if lastoccur[ele] == -1:
			lastoccur[ele] = i
		else:
			val = i - lastoccur[ele] - 1
			lastoccur[ele] = i
			if val < min:
				min = val
	if min == sys.maxsize:
		return 0
	else:
		return n - 1 - min
t = int(input())
l = []
for i in range(t):
	n = int(input())
	S = input()
	result = selection(S)
	l.append(result)
for i in l:
	print(i)


T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	S = input()
	D = {}
	for i in range(N):
		if S[i] in D:
			D[S[i]].append(i)
		else:
			D[S[i]] = [i]
	dist = float('inf')
	for (i, j) in D.items():
		m = float('inf')
		for k in range(len(j) - 1):
			if j[k + 1] - j[k] < m:
				m = j[k + 1] - j[k]
		if m < dist:
			dist = m
	if dist == float('inf'):
		ans.append(0)
	else:
		ans.append(N - dist)
for i in ans:
	print(i)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	d = {}
	l = []
	for i in range(n):
		if s[i] in d:
			l.append(n - i + d[s[i]])
		d[s[i]] = i
	if len(l) == 0:
		print(0)
	else:
		print(max(l))


t = int(input())
for you in range(t):
	n = int(input())
	s = input()
	l = []
	hashi = dict()
	for i in range(n):
		if s[i] in hashi:
			l.append(n - (i - hashi[s[i]]))
		hashi[s[i]] = i
	if l == []:
		print(0)
	else:
		print(max(l))


for _ in range(int(input())):
	n = int(input())
	s = input()
	d = {}
	max = 0
	for i in range(n):
		c = n + d.get(s[i], -n - 1) - i
		if c == n - 1:
			max = c
			break
		d[s[i]] = i
		if c > max:
			max = c
	print(max)


t = int(input())
for x in range(t):
	n = int(input())
	s = input()
	arr = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
	brr = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
	y = 0
	while y < n:
		a = s[y]
		b = ord(a)
		b = b - 97
		if brr[b] == -1:
			brr[b] = y + 1
		else:
			c = y - brr[b]
			if c == 0:
				break
			brr[b] = y + 1
			if arr[b] == -1:
				arr[b] = c
			elif c < arr[b]:
				arr[b] = c
		y = y + 1
	sum = n
	for yy in range(26):
		if arr[yy] != -1 and arr[yy] < sum:
			sum = arr[yy]
	if y != n:
		sum = n - 1
		print(sum)
	elif sum == n:
		sum = 0
		print(sum)
	else:
		n = n - sum
		sum = n - 1
		print(sum)


import math
import sys
from collections import Counter
T = int(input())
for _ in range(0, T):
	N = int(input())
	s = input()
	m = dict()
	mx = 0
	for i in range(0, N):
		if s[i] in m:
			mx = max(mx, N - (i - m[s[i]]))
			m[s[i]] = i
		else:
			m[s[i]] = i
	print(mx)


for _ in range(int(input())):
	N = int(input())
	s = input()
	d = {}
	max_k = 0
	for i in range(N):
		if s[i] in d:
			max_k = max(max_k, N + d[s[i]] - i)
		d[s[i]] = i
	print(max_k)


t = int(input())
for tt in range(t):
	n = int(input())
	s = input()
	d = {}
	mx = 0
	for i in range(len(s)):
		if s[i] not in d:
			d[s[i]] = i
		else:
			mx = max(mx, n - (i - d[s[i]]))
			d[s[i]] = i
	print(mx)


tn = int(input())
for _ in range(tn):
	minv = 999999
	l = [-1] * 26
	n = int(input())
	s = input()
	for j in range(len(s)):
		if l[ord(s[j]) - ord('a')] >= 0:
			temp = j - l[ord(s[j]) - ord('a')]
			if minv > temp:
				minv = temp
			l[ord(s[j]) - ord('a')] = j
		else:
			l[ord(s[j]) - ord('a')] = j
	if minv == 999999:
		print(0)
	else:
		print(len(s) - minv)


from sys import stdin

def solve():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		mini = 100001
		d = dict()
		for i in range(n):
			if s[i] not in d:
				d[s[i]] = i
			else:
				mini = min(mini, i - d[s[i]] - 1)
				d[s[i]] = i
		if mini == 100001:
			print(0)
		else:
			print(n - mini - 1)
solve()


for _ in range(int(input())):
	n = int(input())
	s = input()
	m = 10 ** 9 + 7
	d = dict()
	mi = [m]
	for i in range(n):
		if s[i] not in d:
			d[s[i]] = list()
		if d[s[i]]:
			mi.append(i - d[s[i]][-1])
		d[s[i]].append(i)
	m = min(mi)
	if m == 10 ** 9 + 7:
		print('0')
	else:
		print(n - m)


for _ in range(int(input())):
	(n, s, x, f) = (int(input()), input(), 1, 0)
	for i in range(n):
		for j in range(n - x):
			if s[j] == s[j + x]:
				f = 1
				break
		if f == 1:
			break
		else:
			x += 1
	print(n - x) if bool(f) and x <= n else print(0)


for tc in range(int(input())):
	last = [-1] * 26
	len = 256
	n = int(input())
	str = input()
	for i in range(n):
		if last[ord(str[i]) - 97] == -1:
			last[ord(str[i]) - 97] = i
		else:
			if i - last[ord(str[i]) - 97] - 1 < len:
				len = i - last[ord(str[i]) - 97] - 1
			last[ord(str[i]) - 97] = i
	if len == 256:
		print(0)
	else:
		print(n - len - 1)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	ans = 0
	array = [-1] * 26
	for i in range(n):
		if array[ord(s[i]) - 97] == -1:
			array[ord(s[i]) - 97] = i
		else:
			start = array[ord(s[i]) - 97]
			last = i
			ans = max(ans, n + start - last)
			array[ord(s[i]) - 97] = i
	print(ans)
	t -= 1


ascii_a = ord('a')
t = int(input())
while t:
	t = t - 1
	n = int(input())
	s = list(input())
	mini = n
	lastocc = [-1] * 26
	for i in range(0, n):
		if lastocc[ord(s[i]) - ascii_a] != -1:
			mini = min(i - lastocc[ord(s[i]) - ascii_a], mini)
		lastocc[ord(s[i]) - ascii_a] = i
	print(n - mini)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	d = dict()
	ans = 0
	for i in range(n):
		if s[i] in d:
			ans = max(ans, n - (i - d[s[i]]))
		d[s[i]] = i
	print(ans)


from collections import *
from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	st = stdin.readline()
	lis = [999999999] * 26
	flag = 0
	dic1 = defaultdict(lambda : -1)
	dic2 = defaultdict(lambda : -1)
	alpha = {chr(i): i - 97 for i in range(97, 123)}
	for i in range(n):
		val = st[i]
		ind = alpha[st[i]]
		if dic1[ind] == -1:
			dic1[ind] = i
		elif dic2[ind] == -1:
			dif = i - dic1[ind]
			if dif == 1:
				print(n - 1)
				flag = 1
				break
			dic1[ind] = i
			if lis[ind] > dif:
				lis[ind] = dif
	if not flag:
		fin = n - min(lis)
		if fin < 0:
			print(0)
		else:
			print(fin)


from collections import defaultdict
arr = []
dd = defaultdict(list)

def solve():
	di = {}
	mini = 100001
	N = int(input())
	st = input()
	for i in range(len(st)):
		if st[i] not in di:
			di[st[i]] = i
		else:
			mini = min(mini, i - di[st[i]] - 1)
			di[st[i]] = i
	if mini == 100001:
		print(0)
	else:
		print(N - mini - 1)
T = int(input())
for i in range(T):
	solve()


from collections import defaultdict
import sys
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	D = defaultdict(list)
	for j in range(n):
		if s[j] in D:
			D[s[j]][0] += 1
			if j - D[s[j]][1] < D[s[j]][2]:
				D[s[j]][2] = j - D[s[j]][1]
			D[s[j]][1] = j
		else:
			D[s[j]].append(1)
			D[s[j]].append(j)
			D[s[j]].append(sys.maxsize)
	mini = 0
	for elem in D:
		if D[elem][0] > 1:
			ans = n - D[elem][2]
			if ans > mini:
				mini = ans
	print(mini)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 1000000
	d = {}
	for i in range(n):
		if d.get(s[i]) == None:
			d[s[i]] = [i]
		else:
			d[s[i]].append(i)
	ans = 1000000
	for indices in d.values():
		temp = 1000000
		for j in range(len(indices) - 1):
			temp = min(temp, indices[j + 1] - indices[j])
		ans = min(ans, temp)
	if ans == 1000000:
		print(0)
	else:
		print(n - ans)


for _ in range(int(input())):
	a = int(input())
	j = input()
	answer = 1000000
	q = {}
	for i in range(a):
		if q.get(j[i]) == None:
			q[j[i]] = [i]
		else:
			q[j[i]].append(i)
	answer = 1000000
	for indices in q.values():
		temp = 1000000
		for j in range(len(indices) - 1):
			temp = min(temp, indices[j + 1] - indices[j])
		answer = min(answer, temp)
	if answer == 1000000:
		print(0)
	else:
		print(a - answer)


for t in range(int(input())):
	minv = 1000
	n = int(input())
	s = str(input())
	arr = [-1] * 26
	for (i, x) in enumerate(s):
		if arr[ord(s[i]) - ord('a')] >= 0:
			temp = i - arr[ord(s[i]) - ord('a')]
			minv = min(temp, minv)
			arr[ord(s[i]) - ord('a')] = i
		else:
			arr[ord(s[i]) - ord('a')] = i
	if minv == 1000:
		print(0)
	else:
		print(len(s) - minv)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	ans = 0
	d = defaultdict(lambda : -1)
	s = input()
	for (i, j) in enumerate(s):
		if d[ord(j)] > -1:
			ans = max(ans, n - (i - d[ord(j)]))
		d[ord(j)] = i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	f = 0
	e = []
	dic = {}
	idic = {}
	i = 0
	while i < len(s):
		x = s[i]
		if x in dic:
			r = dic[x]
			r = r + 1
			dic[x] = r
			pi = idic[x]
			idic[x] = i
			dif = i - pi - 1
			e.append(dif)
			if f == 0:
				f = 1
		else:
			dic[x] = 1
			idic[x] = i
		i = i + 1
	if f == 0:
		print(0)
	else:
		e.sort()
		t = e[0]
		o = len(s) - t - 1
		print(o)


import sys
for _ in range(int(input())):
	input()
	string = input()
	minDiff = sys.maxsize
	freq = dict()
	ans = sys.maxsize
	for i in range(len(string)):
		if string[i] in freq.keys():
			freq[string[i]].append(i)
		else:
			freq[string[i]] = [i]
	for i in freq.keys():
		minDiff = sys.maxsize
		for l in range(len(freq[i]) - 1):
			minDiff = min(minDiff, freq[i][l + 1] - freq[i][l])
		ans = min(ans, minDiff)
	if ans == sys.maxsize:
		print(0)
	else:
		print(len(string) - ans)


try:
	for _ in range(int(input())):
		n = int(input())
		s = input()
		d = {}
		ans = 1000000
		for i in range(n):
			if s[i] in d:
				d[s[i]].append(i)
			else:
				d[s[i]] = [i]
		for i in d.values():
			mi = 1000000
			for j in range(len(i) - 1):
				mi = min(mi, i[j + 1] - i[j])
			ans = min(mi, ans)
		if ans == 1000000:
			print(0)
		else:
			print(n - ans)
except:
	pass


from collections import defaultdict

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = input()
		last_pos = defaultdict(lambda : -1)
		min_diff = n
		for (i, ch) in enumerate(s):
			if last_pos[ch] != -1:
				min_diff = min(min_diff, i - last_pos[ch])
			last_pos[ch] = i
		print(n - min_diff)
main()


import sys
turn = int(input())
min = sys.maxsize
track = 0
for _ in range(turn):
	min = sys.maxsize
	l = {'a': -1, 'b': -1, 'n': -1, 'm': -1, 'l': -1, 'k': -1, 'j': -1, 'i': -1, 'h': -1, 'g': -1, 'f': -1, 'e': -1, 'd': -1, 'c': -1, 'o': -1, 'p': -1, 'q': -1, 'z': -1, 'y': -1, 'x': -1, 'w': -1, 'v': -1, 'u': -1, 't': -1, 's': -1, 'r': -1}
	track = 0
	k = int(input())
	s = str(input())
	c = 0
	for i in s:
		if l[i] != -1:
			k = c - l[i]
		l[i] = c
		if min > k:
			min = k
			track = c
		c += 1
	print(len(s) - min)


for t in range(int(input())):
	n = int(input())
	s = list(input().strip())
	a = {}
	ans = 0
	for i in range(n):
		if s[i] not in a.keys():
			a[s[i]] = i + 1
		else:
			if ans < a[s[i]] + (n - i - 1):
				ans = a[s[i]] + (n - i - 1)
			a[s[i]] = i + 1
	print(ans)


t = int(input())
while t:
	t -= 1
	distances = [9999999] * 26
	dic = dict()
	n = int(input())
	string = input()
	i = 0
	for ch in string:
		if ch in dic:
			currentDistance = i - dic[ch]
			if currentDistance < distances[ord(ch) - 97]:
				distances[ord(ch) - 97] = currentDistance
			dic[ch] = i
		else:
			dic[ch] = i
		i += 1
	minimumDistance = min(distances)
	if minimumDistance == 9999999:
		print('0')
	else:
		print(n - minimumDistance)


def adjacent_ch(s, n):
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			return True
	return False
for _ in range(int(input())):
	n = int(input())
	s = input()
	freq = [0] * 26
	for i in s:
		freq[ord(i) - ord('a')] += 1
	flag = 0
	for i in freq:
		if i >= 2:
			flag = 1
			break
	if flag == 0:
		print(0)
	elif adjacent_ch(s, n):
		print(n - 1)
	else:
		d = dict()
		for i in range(n):
			if s[i] not in d:
				d[s[i]] = [i]
			else:
				d[s[i]].append(i)
		ans = n
		for v in d.values():
			if len(v) > 1:
				for i in range(len(v) - 1):
					ans = min(ans, v[i + 1] - v[i])
		ans -= 1
		n = n - ans
		print(n - 1)


t = int(input())
while t > 0:
	n = int(input())
	s = str(input())[0:n]
	uni = set(s)
	letr = {k: -1 for k in uni}
	min = n
	flag = 0
	for i in range(0, n):
		if letr[s[i]] == -1:
			letr[s[i]] = i
		else:
			temp = i - letr[s[i]]
			if min > temp:
				min = temp
			letr[s[i]] = i
	print(n - min)
	t -= 1


t = int(input())
while t:
	t = t - 1
	n = int(input())
	s = input()
	dic = {}
	a = n
	for i in range(n):
		if s[i] in dic:
			tt = i - dic[s[i]]
			dic[s[i]] = i
			if tt < a:
				a = tt
		else:
			dic[s[i]] = i
	print(n - a)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	s_len = len(s)
	rep_dict = {}
	rep_with_least_dist = s_len + 1
	for (i, ch) in enumerate(s):
		if rep_dict.get(ch, -1) != -1:
			rep_with_least_dist = min(rep_with_least_dist, i - rep_dict[ch])
		rep_dict[ch] = i
	if rep_with_least_dist != s_len + 1:
		print(s_len - rep_with_least_dist)
	else:
		print('0')
	t -= 1


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	d = {}
	k = n
	for i in range(n):
		if s[i] not in d:
			d[s[i]] = i
		else:
			m = i - d[s[i]]
			if m < k:
				k = m
			d[s[i]] = i
	print(n - k)


t = int(input())
for T in range(t):
	n = int(input())
	s = input()
	(val, k) = (0, n)
	d = {}
	for i in range(n):
		if s[i] in d:
			val = i - d[s[i]]
			if val < k:
				k = val
		d[s[i]] = i
	print(n - k)


for t in range(int(input())):
	n = int(input())
	s = input()
	d = {}
	ans = 0
	for i in range(n):
		if s[i] not in d:
			d[s[i]] = [i]
		else:
			d[s[i]].append(i)
	min = 9999999999
	for i in d:
		if len(d[i]) > 1:
			for j in range(1, len(d[i])):
				if d[i][j] - d[i][j - 1] < min:
					min = d[i][j] - d[i][j - 1]
	if min == 9999999999:
		ans = 0
	else:
		ans = n - min
	print(ans)


import sys
t = int(input())

def findLongestSeq(n, inp):
	minDiff = sys.maxsize
	charPos = [-1] * 26
	for i in range(n):
		c = inp[i]
		numericChar = ord(c) - 98
		if charPos[numericChar] == -1:
			charPos[numericChar] = i
		else:
			minDiff = min(minDiff, i - charPos[numericChar])
			charPos[numericChar] = i
	return 0 if minDiff is sys.maxsize else n - minDiff
for _ in range(t):
	n = int(input())
	inp = input()
	print(findLongestSeq(n, inp))


T = int(input())
t = 0
while t < T:
	t += 1
	N = int(input())
	S = input()
	D = [-1 for i in range(26)]
	ans = N + 1
	for (j, x) in enumerate(S):
		i = ord(x) - ord('a')
		if D[i] != -1:
			ans = min(ans, j - D[i])
		D[i] = j
	ans = N - ans if ans != N + 1 else 0
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = input()
	res = 0
	flag = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			if arr[i] == arr[j]:
				res = max(res, n - (j - i))
				if j == i + 1:
					flag = 1
				break
		if flag:
			break
	print(res)


def main(debug=False):
	for _ in range(int(input())):
		n = int(input())
		s = input().strip()
		d = {}
		ans = 0
		for i in range(n):
			if s[i] in d:
				ans = max(ans, n - (i - d[s[i]]))
			d[s[i]] = i
		print(ans)
while True:
	try:
		main(debug=False)
	except (ValueError, EOFError) as e:
		break


for _ in range(int(input())):
	n = int(input())
	s = list(input().strip())
	d = {}
	ans = 0
	for i in range(len(s)):
		if s[i] in d:
			ans = max(ans, n - (i - d[s[i]]))
		else:
			d[s[i]] = i
		d[s[i]] = i
	print(ans)


for i in range(int(input())):
	n = int(input())
	s = input()
	d = {}
	k = n
	for j in range(len(s)):
		if s[j] not in d:
			d[s[j]] = j
		else:
			v = j - d[s[j]]
			if v < k:
				k = v
			d[s[j]] = j
	print(n - k)


t = int(input())
while t > 0:
	n = int(input())
	st = input()
	min = n
	for i in range(n):
		idx = st.find(st[i], i + 1, n)
		if idx != -1:
			if idx - i < min:
				min = idx - i
	if min == n:
		print(0)
	else:
		print(n - min)
	t = t - 1


from string import ascii_lowercase
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ch = {}
	for c in ascii_lowercase:
		ch[c] = []
	for (i, c) in enumerate(s):
		ch[c].append(i)
	val = 0
	for (k, v) in ch.items():
		for (i, indx) in enumerate(v):
			if i != len(v) - 1:
				next = v[i + 1]
				val = max(val, n - (next - indx))
	print(val)


a = int(input())
for i in range(0, a):
	b = int(input())
	c = input()
	d = [100] * 26
	mi = 1000
	val = 100
	for j in range(0, b):
		if d[ord(c[j]) - 97] == 100:
			d[ord(c[j]) - 97] = j
		else:
			val = j - d[ord(c[j]) - 97] - 1
			d[ord(c[j]) - 97] = j
			if mi > val:
				mi = val
	if mi == 1000:
		print(0)
	else:
		print(b - 1 - mi)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	m = n + 1
	if len(set(s)) == n:
		print(0)
	else:
		d = dict()
		for j in range(n):
			ch = s[j]
			if ch in d.keys():
				m = min(m, j - d[ch])
			d[ch] = j
		print(n - m)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	l_a = [-1] * 26
	mid = float('inf')
	for i in range(len(s)):
		if l_a[ord(s[i]) - ord('a')] != -1:
			mid = min(i - l_a[ord(s[i]) - ord('a')] - 1, mid)
		l_a[ord(s[i]) - ord('a')] = i
	if mid == float('inf'):
		print('0\n')
	else:
		print(n - 1 - mid, '\n')


import sys
print = sys.stdout.write
for _ in range(int(input())):
	n = int(input())
	st = input()
	d = {}
	min_diff = n
	for i in range(n):
		char = st[i]
		if char not in d:
			d[char] = i
		else:
			a = d[char]
			b = i
			diff = b - a
			d[char] = i
			if diff < min_diff:
				min_diff = diff
	print(f'{n - min_diff}\n')


for _ in range(int(input())):
	n = int(input())
	dic = {}
	string = input()
	k = 9999999
	for i in range(n):
		if string[i] not in dic:
			dic[string[i]] = i
		else:
			if k > abs(dic[string[i]] - i) - 1:
				k = abs(dic[string[i]] - i) - 1
			dic[string[i]] = i
	if k == 9999999:
		print(0)
	else:
		print(n - 1 - k)


t = int(input())
for _ in range(t):
	n = int(input())
	st = input()
	mi = n
	lst_count = [-1] * 26
	for i in range(n):
		if lst_count[ord(st[i]) - 97] == -1:
			lst_count[ord(st[i]) - 97] = i
		else:
			mi = min(mi, i - lst_count[ord(st[i]) - 97])
			lst_count[ord(st[i]) - 97] = i
	print(n - mi)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = 0
	d = {}
	for i in range(n):
		if s[i] in d:
			a = max(a, n - (i - d[s[i]]))
			d[s[i]] = i
		else:
			d[s[i]] = i
	print(a)


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	l = [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
	dic = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
	leng = 0
	maxi = 0
	temp = 0
	for i in range(0, n):
		sw = int(dic[s[i]])
		l[sw].append(i)
	for i in range(0, 26):
		if len(l[i]) > 1:
			for j in range(0, len(l[i]) - 1):
				temp = n - l[i][j + 1] + l[i][j]
				maxi = max(maxi, temp)
	print(maxi)


def firstrepeated(str):
	min = 10000000
	c2 = 0
	for i in range(0, len(str)):
		c2 = str.find(str[i], i + 1)
		if min >= c2 - i and c2 - i > 0:
			min = c2 - i
	return min
t = int(input())
while t > 0:
	n = int(input())
	str = input()
	set1 = set()
	for i in range(0, len(str)):
		set1.add(str[i])
	if len(set1) == n:
		print('0')
		t = t - 1
		continue
	else:
		k = firstrepeated(str)
		print(len(str) - k)
	t = t - 1


T = int(input())
for t in range(T):
	N = int(input())
	S = input()
	D = {}
	M = N
	for i in range(N):
		if S[i] in D:
			d = i - D[S[i]][0]
			if d < D[S[i]][1] or not D[S[i]][1]:
				D[S[i]][1] = d
			D[S[i]][0] = i
		else:
			D[S[i]] = [i, 0]
	for i in range(N):
		if D[S[i]][1] < M and D[S[i]][1]:
			M = D[S[i]][1]
	print(N - M)


try:
	from collections import defaultdict

	def sol(str):
		hm = defaultdict(int)
		ans = 0
		for i in range(len(str)):
			if str[i] in hm:
				ans = max(ans, len(str) - (i - hm[str[i]]))
			hm[str[i]] = i
		print(ans)
	t = int(input())
	while t > 0:
		n = int(input())
		str = input()
		sol(str)
		t = t - 1
except:
	pass


t = int(input())
while t > 0:
	n = int(input())
	s = list(input())
	l = {}
	ans = 0
	for i in range(n):
		if s[i] in l.keys():
			ans = max(ans, n - (i - l[s[i]]))
		l[s[i]] = i
	print(ans)
	t -= 1


t = int(input())
while t != 0:
	n = int(input())
	s = input()
	mi = [n + 3] * 26
	cd = [-1] * 26
	j = 0
	for i in s:
		if cd[ord(i) - 97] == -1:
			cd[ord(i) - 97] = j
		else:
			dis = j - cd[ord(i) - 97]
			if mi[ord(i) - 97] > dis:
				mi[ord(i) - 97] = dis
			cd[ord(i) - 97] = j
		j += 1
	bn = n
	for x in mi:
		if x < bn:
			bn = x
	print(n - bn)
	t -= 1


t = int(input())
while t:
	length = int(input())
	s = input()
	pos = [-1] * 26
	l = [999999] * 26
	for i in range(length):
		x = ord(s[i]) - 97
		if pos[x] == -1:
			pos[x] = i
		else:
			if i - pos[x] < l[x]:
				l[x] = i - pos[x]
			pos[x] = i
	if min(l) == 999999:
		print(0)
	else:
		print(length - min(l))
	t = t - 1


from collections import defaultdict
import sys
for _ in range(int(input())):
	d = defaultdict(lambda : 0)
	n = int(input())
	mini = sys.maxsize
	f = 0
	s = input()
	for i in range(n):
		if d[s[i]] == 0:
			d[s[i]] = i + 1
		else:
			f = 1
			dis = abs(i + 1 - d[s[i]])
			if dis < mini:
				mini = dis
			d[s[i]] = i + 1
	if f == 0:
		print(0)
	else:
		print(n - mini)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	a = {}
	count = n
	for i in range(n):
		if s[i] in a:
			d = i - a[s[i]][0]
			if d < a[s[i]][1] or not a[s[i]][1]:
				a[s[i]][1] = d
			a[s[i]][0] = i
		else:
			a[s[i]] = [i, 0]
	for i in a:
		if a[i][1] < count and a[i][1]:
			count = a[i][1]
	print(n - count)


for _ in range(int(input())):
	n = int(input())
	s = input()
	mp = {}
	k = n
	val = 0
	for i in range(n):
		if s[i] in mp:
			val = i - mp[s[i]]
			if val < k:
				k = val
			mp[s[i]] = i
		else:
			mp[s[i]] = i
	print(n - k)


for _ in range(int(input())):
	n = int(input())
	s = input()
	d = {}
	m = n
	dif = 0
	for i in range(n):
		if s[i] in d:
			dif = i - d[s[i]]
			if dif < m:
				m = dif
			d[s[i]] = i
		else:
			d[s[i]] = i
	print(n - m)


t = int(input())
while t > 0:
	minv = 999999
	l = [-1] * 26
	n = int(input())
	s = input()
	for j in range(len(s)):
		if l[ord(s[j]) - ord('a')] >= 0:
			temp = j - l[ord(s[j]) - ord('a')]
			if minv > temp:
				minv = temp
			l[ord(s[j]) - ord('a')] = j
		else:
			l[ord(s[j]) - ord('a')] = j
	if minv == 999999:
		print('0')
	else:
		print(len(s) - minv)
	t -= 1


T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	res = 0
	prev = {}
	for i in range(n):
		if s[i] in prev:
			res = max(res, n - i + prev[s[i]])
		prev[s[i]] = i
	print(res)


T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	minv = 999999
	prev = [-1] * 26
	for j in range(n):
		if prev[ord(s[j]) - ord('a')] >= 0:
			temp = j - prev[ord(s[j]) - ord('a')]
			if temp < minv:
				minv = temp
			prev[ord(s[j]) - ord('a')] = j
		else:
			prev[ord(s[j]) - ord('a')] = j
	if minv == 999999:
		print(0)
	else:
		print(n - minv)


INT32_MAX = 2147483647
T = int(input())
for i in range(T):
	n = int(input())
	string = input()
	least = {}
	for i in range(ord('a'), ord('z') + 1):
		least[chr(i)] = [-1, INT32_MAX]
	for i in range(n):
		char = string[i]
		if least[char][0] != -1:
			difference = i - least[char][0]
			if difference < least[char][1]:
				least[char][1] = difference
		least[char][0] = i
	mn = INT32_MAX
	for i in least:
		if least[i][1] < mn:
			mn = least[i][1]
	if mn == INT32_MAX:
		print(0)
		continue
	print(n - mn)


import sys
t = int(input())
while t:
	n = int(input())
	s = input()
	k = 0
	l2 = set(s)
	if n == len(l2):
		k = 0
	else:
		l3 = [-1 for i in range(26)]
		m = n
		for i in range(n):
			c = ord(s[i])
			if l3[c - 97] == -1:
				l3[c - 97] = i
			else:
				x = l3[c - 97]
				l3[c - 97] = i
				if i - x < m:
					m = i - x
		k = n - m
	print(k)
	t = t - 1


import sys
for t in range(int(input())):
	n = int(input())
	s = input()
	ind = {}
	for i in range(n):
		if s[i] in ind:
			ind[s[i]].append(i)
		else:
			ind[s[i]] = [i]
	min_diff = sys.maxsize
	for same_element_index in ind.values():
		for i in range(len(same_element_index) - 1):
			min_diff = min(min_diff, same_element_index[i + 1] - same_element_index[i])
	ans = n - min_diff if min_diff < sys.maxsize else 0
	print(ans)