Gotham City is the home of Batman, and Batman likes to keep his people together. 

There are N houses in the city. The resident of the i^{th} house is of type A_{i}. It is known that people of the same type are friends and people of different types are not friends. 

To maintain peace, Batman can do the following type of operation:
Choose indices i and j (1≤ i ≤ j ≤ N) and reverse the substring A[i,j]. 

Determine the length of the longest range of friends after applying at most k operations on the string for all 0 ≤ k ≤ N.

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

- First line will contain T, the number of test cases. Then the test cases follow.
- The first line of each test case contains a single integer N, the number of houses in Gotham city.
- The next line contains a string A with N characters. The i^{th} character denotes the type of the i^{th} person.

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

For each test case, output a single line, (N+1) space-separated integers where the i^{th} integer signifies the length of the longest range of friends after applying  at most i operations.

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

$1 ≤ T ≤ 1000$
$1≤N ≤2\cdot 10^{5}$
- Sum of $N$ over all test cases does not exceed $2\cdot 10^{5}$.
- String $A$ contains lowercase English alphabets only.

----- Sample Input 1 ------ 
3
4
aaaa
4
abca
7
babbaab

----- Sample Output 1 ------ 
4 4 4 4 4
1 2 2 2 2
2 3 4 4 4 4 4 4

----- explanation 1 ------ 
Test case $1$: All $4$ people are friends. Thus, the answer is $4$ for all values of $k$.

Test case $2$: 
- For $k=0$, the length of the longest range of friends is $1$.
- For $k=1$, we can choose $i=1$ and $j=3$. On reversing the substring $[1,3]$, we get cbaa. Thus, length of longest range of friends is $2$.
- For $k=2,3,$ and $4$, the length of the longest range of friends is $2$ as no more people of the same type can be grouped together.

Difficulty: HARD
Tags: String algorithms

Dynamic programming

Data structures

Mathematics
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
from audioop import reverse
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	dic = {}
	for i in range(n):
		if s[i] in dic:
			dic[s[i]] += 1
		else:
			dic[s[i]] = 1
	ma = 0
	tp = ''
	for i in dic:
		if dic[i] > ma:
			ma = dic[i]
			tp = i
	dic = {}
	prev = -1
	c = 0
	for i in range(n):
		if s[i] != prev:
			if prev != -1:
				if prev in dic:
					dic[prev].append(c)
				else:
					dic[prev] = [c]
			c = 1
			prev = s[i]
			if i == n - 1:
				if prev in dic:
					dic[prev].append(c)
				else:
					dic[prev] = [c]
		else:
			c += 1
			if i == n - 1:
				if prev in dic:
					dic[prev].append(c)
				else:
					dic[prev] = [c]
	li = []
	for i in dic:
		nli = dic[i]
		nli.sort(reverse=True)
		li.append([i, nli, 1, nli[0]])
	ans = []
	for i in range(n + 1):
		tempmax = []
		for j in range(len(li)):
			nli = li[j][1]
			tempmax.append(li[j][3])
			if li[j][2] < len(nli):
				li[j][3] += nli[li[j][2]]
				li[j][2] += 1
		ans.append(max(tempmax))
	print(*ans)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	s = input()
	prev = None
	temp = 0
	d = defaultdict(list)
	for (i, el) in enumerate(s):
		if not prev or prev == el:
			temp += 1
		else:
			d[prev].append(temp)
			temp = 1
		prev = el
	d[prev].append(temp)
	for j in range(26):
		ch = chr(ord('a') + j)
		if len(d[ch]):
			d[ch].sort(reverse=True)
			for i in range(1, len(d[ch])):
				d[ch][i] += d[ch][i - 1]
	res = []
	for i in range(n + 1):
		p = 0
		for j in range(26):
			ch = chr(ord('a') + j)
			if len(d[ch]):
				ind = min(i, len(d[ch]) - 1)
				p = max(p, d[ch][ind])
		res.append(p)
	print(*res)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	s = s + '$'
	cnt = 0
	alphafreq = [[] for _ in range(26)]
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			cnt += 1
		else:
			alphafreq[ord(s[i - 1]) - ord('a')].append(cnt + 1)
			cnt = 0
	for i in range(26):
		alphafreq[i].sort(reverse=True)
		for j in range(1, len(alphafreq[i])):
			alphafreq[i][j] += alphafreq[i][j - 1]
	ans = []
	for i in range(n + 1):
		curr = 0
		for j in range(26):
			if alphafreq[j]:
				curr = max(curr, alphafreq[j][-1 if i >= len(alphafreq[j]) else i])
		ans.append(curr)
	print(*ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	ss = [[] for i in range(26)]
	ss_size = [0] * 26
	(curr, cnt) = (None, 0)
	for ch in s:
		if curr is None:
			curr = ch
			cnt += 1
		elif curr == ch:
			cnt += 1
		else:
			ss[ord(curr) - 97].append(cnt)
			ss_size[ord(curr) - 97] += 1
			curr = ch
			cnt = 1
	ss[ord(curr) - 97].append(cnt)
	ss_size[ord(curr) - 97] += 1
	for ch_ss in ss:
		ch_ss.sort(reverse=True)
	k_mx = [0] * (n + 1)
	ans = [0] * 26
	for i in range(n + 1):
		for j in range(26):
			if i < ss_size[j]:
				ans[j] += ss[j][i]
		k_mx[i] = max(ans)
	print(' '.join(map(str, k_mx)))


import sys, string as strr
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	n = int(input())
	s = input() + '$'
	cnt = 0
	alphafreq = [[] for _ in range(26)]
	for i in range(1, len(s)):
		eq = s[i] == s[i - 1]
		if not eq:
			alphafreq[strr.ascii_lowercase.index(s[i - 1])].append(cnt + 1)
		cnt = cnt * eq + eq
	for i in range(26):
		alphafreq[i].sort(reverse=True)
		for j in range(1, len(alphafreq[i])):
			alphafreq[i][j] += alphafreq[i][j - 1]
	ans = []
	for i in range(n + 1):
		curr = 0
		for j in range(26):
			if alphafreq[j]:
				curr = max(curr, alphafreq[j][i if i < len(alphafreq[j]) else -1])
		ans.append(curr)
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	s = input() + '$'
	cnt = 0
	alphafreq = [[] for _ in range(26)]
	for i in range(1, len(s)):
		eq = s[i] == s[i - 1]
		if not eq:
			alphafreq['abcdefghijklmnopqrstuvwxyz'.index(s[i - 1])].append(cnt + 1)
		cnt = cnt * eq + eq
	for i in range(26):
		alphafreq[i].sort(reverse=True)
		for j in range(1, len(alphafreq[i])):
			alphafreq[i][j] += alphafreq[i][j - 1]
	ans = []
	for i in range(n + 1):
		curr = 0
		for j in range(26):
			if alphafreq[j]:
				curr = max(curr, alphafreq[j][i if i < len(alphafreq[j]) else -1])
		ans.append(curr)
	print(*ans)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = input()
	dp = Counter(arr)
	mx = dp[arr[0]]
	index = arr[0]
	st = [['xx'] for i in range(26)]
	for index in dp:
		for i in arr:
			if i == index and st[ord(index) - 97][-1].isdigit():
				st[ord(index) - 97].append(str(int(st[ord(index) - 97].pop()) + 1))
			elif i == index:
				st[ord(index) - 97].append('1')
			else:
				st[ord(index) - 97].append(i)
	ans = []
	k = 0
	for x in st:
		a = []
		for i in x:
			if i.isdigit():
				a.append(int(i))
		if len(x) > 1:
			ans.append(sorted(a, reverse=True))
	dp = [0] * (n + 1)
	for k in range(len(ans)):
		ans[k] += [0 for i in range(n - len(ans[k]) + 1)]
		dp[0] = max(ans[k][0], dp[0])
		for i in range(1, len(ans[k])):
			ans[k][i] += ans[k][i - 1]
			dp[i] = max(dp[i], ans[k][i])
	print(dp[0], end=' ')
	for i in range(1, n + 1):
		dp[i] = max(dp[i], dp[i - 1])
		print(dp[i], end=' ')
	print()


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

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

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

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

def printyes():
	print('YES')

def printno():
	print('NO')
for t in range(int(input())):
	n = ni()
	s = si() + '&'
	new = []
	i = 0
	pre = 0
	while i < len(s) - 1:
		if s[i + 1] != s[i]:
			new.append(s[pre:i + 1])
			pre = i + 1
		i += 1
	s = list(new)
	d = dict()
	for i in s:
		if i[0] not in d:
			d[i[0]] = []
		d[i[0]].append(len(i))
	for i in d:
		d[i].sort(reverse=True)
		for j in range(1, len(d[i])):
			d[i][j] += d[i][j - 1]
	a = set(d.keys())
	ans = [0]
	for i in range(n + 1):
		re = []
		curr = ans[-1]
		for j in a:
			if len(d[j]) == i + 1:
				re.append(j)
			curr = max(curr, d[j][i])
		ans.append(curr)
		for j in re:
			a.remove(j)
	ans.pop(0)
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	a = input()
	d = dict()
	for i in a:
		d[i] = -1
	counter = 0
	for i in a:
		if d[i] == -1:
			d[i] = counter
			counter += 1
	result = []
	for i in range(counter):
		temp = []
		result.append(temp)
	s = a[i]
	count = 0
	for i in a:
		if i != s:
			result[d[s]].append(count)
			count = 1
			s = i
		else:
			count += 1
	result[d[s]].append(count)
	for lis in result:
		lis.sort(reverse=True)
		l = len(lis)
		while l < n + 1:
			lis.append(0)
			l += 1
		summ = 0
		for i in range(l):
			summ += lis[i]
			lis[i] = summ
	ans = []
	for i in range(n + 1):
		maxx = 0
		for j in range(counter):
			if result[j][i] > maxx:
				maxx = result[j][i]
		ans.append(maxx)
	print(*ans)


from collections import defaultdict
import sys
input = sys.stdin.readline
t = int(input())

def solve():
	N = int(input())
	d = defaultdict(list)
	A = input().strip('\n')
	curr = A[0]
	run = 1
	for x in A[1:]:
		if x == curr:
			run += 1
		else:
			d[curr].append(run)
			run = 1
			curr = x
	d[curr].append(run)
	ans = [0] * (N + 1)
	for nums in d.values():
		nums.sort()
		i = 0
		j = len(nums) - 1
		s = sum(nums)
		while i <= j:
			if ans[j - i] < s:
				ans[j - i] = s
			if nums[i] <= nums[j]:
				s -= nums[i]
				i += 1
			else:
				s -= nums[j]
				j -= 1
	for i in range(1, N + 1):
		ans[i] = max(ans[i], ans[i - 1])
	print(*ans)
while t:
	solve()
	t -= 1


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

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

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		n = inpu()
		s = inp()
		l = defaultdict(list)
		cnt = 1
		for i in range(1, n):
			if s[i] == s[i - 1]:
				cnt += 1
			else:
				l[s[i - 1]].append(cnt)
				cnt = 1
		l[s[-1]].append(cnt)
		for i in l:
			l[i].sort(reverse=True)
			l[i] = list(accumulate(l[i]))
		ans = []
		j = 0
		for i in range(n):
			p = -inf
			for i in l:
				if j < len(l[i]):
					p = max(p, l[i][j])
			j += 1
			if len(ans) == 0:
				ans.append(p)
			else:
				ans.append(max(ans[-1], p))
		ans.append(ans[-1])
		print(*ans)
main()


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	ran = [[] for i in range(26)]
	cnt = 0
	cur = '.'
	for i in range(n):
		if s[i] == cur:
			cnt += 1
		else:
			if cnt > 0:
				ran[ord(cur) - ord('a')].append(cnt)
			cnt = 1
			cur = s[i]
	ran[ord(cur) - ord('a')].append(cnt)
	ans = [1 for i in range(n + 1)]
	for r in ran:
		r.sort(reverse=True)
		tmp = 0
		for i in range(len(r)):
			tmp += r[i]
			ans[i] = max(ans[i], tmp)
	for i in range(1, n + 1):
		ans[i] = max(ans[i], ans[i - 1])
	print(*ans)


t = int(input())
while t:
	t -= 1
	x = int(input())
	st = input()
	st = st + '.'
	c = 0
	cont = [[] for i in range(26)]
	pre = st[0]
	for i in st:
		if i == pre:
			c += 1
		else:
			cont[ord(pre) - ord('a')].append(c)
			c = 1
		pre = i
	for i in range(26):
		cont[i].sort(reverse=True)
	tg = [0 for i in range(26)]
	score = [0 for i in range(26)]
	for i in range(26):
		if len(cont[i]) == 0:
			tg[i] = 1
	for i in range(x + 1):
		ma = 0
		for j in range(26):
			if i >= len(cont[j]):
				tg[j] = 1
			if tg[j] == 1:
				ma = max(score[j], ma)
			else:
				score[j] += cont[j][i]
				ma = max(score[j], ma)
		print(ma, end=' ')
	print()


from collections import Counter
t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	key = list(Counter(s).keys())
	x = []
	for i in range(len(key)):
		y = [0] * (n + 1)
		x.append(y)
	y = []
	for i in range(len(key)):
		ct = 0
		k = 0
		for j in range(n):
			if s[j] == key[i]:
				k += 1
			else:
				x[i][ct] = k
				k = 0
				ct += 1
		x[i][ct] = k
		k = 0
	for i in range(len(key)):
		x[i].sort(reverse=True)
	for i in range(len(key)):
		x11 = 0
		for it in range(n):
			x[i][it] += x11
			x11 = x[i][it]
	ans = 0
	ans1 = []
	for i in range(n):
		for j in range(len(key)):
			ans = max(ans, x[j][i])
		ans1.append(ans)
	ans1.append(ans1[-1])
	print(*ans1)


for _ in range(int(input())):
	N = int(input())
	S = input()
	dict = {}
	for i in range(N):
		if S[i] in dict:
			dict[S[i]] += 1
		else:
			dict[S[i]] = 1
	ans = [0] * (N + 1)
	for i in dict:
		temp = []
		actual_size = 0
		curr = 0
		for j in range(N):
			if S[j] == i:
				curr += 1
			else:
				actual_size = curr
				if actual_size > 0:
					temp.append(actual_size)
				(actual_size, curr) = (0, 0)
		if curr != 0:
			temp.append(curr)
		temp.sort(reverse=True)
		temp_ans = [0] * (N + 1)
		temp_ans[0] = temp[0]
		for j in range(1, N + 1):
			if j < len(temp):
				temp_ans[j] = temp_ans[j - 1] + temp[j]
			else:
				temp_ans[j] = temp_ans[j - 1]
		for j in range(N + 1):
			ans[j] = max(ans[j], temp_ans[j])
	print(*ans)


import sys
from math import sqrt, gcd, factorial, ceil, floor, pi
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	n = I()
	s = S()
	x = 'abcdefghijklmnopqrstuvwxyz'
	d = {i: [] for i in x}
	i = 0
	while i < n:
		(c, j) = (1, i + 1)
		while j < n and s[j] == s[i]:
			c += 1
			j += 1
		d[s[i]].append(c)
		i = j
	for i in d:
		d[i].sort(reverse=True)
		d[i] += [0] * (n + 1 - len(d[i]))
		for j in range(1, n + 1):
			d[i][j] += d[i][j - 1]
	ans = []
	for k in range(n + 1):
		val = 0
		for i in d:
			val = max(val, d[i][k])
		ans.append(val)
	print(*ans)


def postprocess(arr):
	di = {}
	for i in arr:
		if i[0] in di:
			di[i[0]].append(len(i) + di[i[0]][-1])
		else:
			di[i[0]] = [len(i)]
	return di

def preprocess(A, x):
	L = []
	l = A[0]
	for i in range(1, x):
		if A[i - 1] == A[i]:
			l += A[i]
		else:
			L.append(l)
			l = A[i]
	if len(l) > 0:
		L.append(l)
	L.sort(key=lambda x: len(x), reverse=True)
	return L
for _ in range(int(input())):
	size = int(input())
	st = input()
	L1 = preprocess(st, size)
	L = postprocess(L1)
	answer = [0 for i in range(size + 1)]
	for i in range(size):
		for j in L:
			if i > len(L[j]) - 1:
				answer[i] = max(answer[i], L[j][-1])
				continue
			answer[i] = max(answer[i], L[j][i])
	answer[-1] = max(answer)
	print(*answer)


for _ in range(int(input())):
	n = int(input())
	a = input()
	streaks = []
	current = []
	o = {x: [] for x in a}
	for (i, item) in enumerate(a):
		if not current:
			current = [item]
		elif item == current[-1]:
			current.append(item)
		else:
			streaks.append(current)
			current = [item]
	if current:
		streaks.append(current)
	for item in streaks:
		o[item[0]].append(len(item))
	for (key, value) in o.items():
		o[key] = sorted(value)[::-1]
	o_prefix = {}
	for (key, value) in o.items():
		e = []
		for (i, item) in enumerate(value):
			k = item
			if i:
				k += e[-1]
			e.append(k)
		o_prefix[key] = e
	results = []
	for i in range(n + 1):
		max_so_far = float('-inf')
		for (j, thing) in enumerate(o_prefix.values()):
			try:
				max_so_far = max(max_so_far, thing[i])
			except:
				pass
		if max_so_far == float('-inf'):
			max_so_far = results[-1]
		if results and results[-1] > max_so_far:
			max_so_far = results[-1]
		results.append(max_so_far)
	print(*results)


from collections import defaultdict
import heapq
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	hashmap = defaultdict(list)
	hashmap[s[0]].append(-1)
	for i in range(1, n):
		if s[i] == s[i - 1]:
			hashmap[s[i]][-1] -= 1
		else:
			hashmap[s[i]].append(-1)
	for key in hashmap:
		heapq.heapify(hashmap[key])
	best_lengths = dict()
	for key in hashmap:
		best_lengths[key] = 0
	answer = []
	for i in range(n + 1):
		for key in hashmap:
			if hashmap[key]:
				best_lengths[key] -= heapq.heappop(hashmap[key])
		answer.append(max(best_lengths.values()))
	print(' '.join([str(x) for x in answer]))


from sys import stdin, stdout, setrecursionlimit
import collections
import math

def solve(root):
	if tree[root]:
		c = 0
		for n in tree[root]:
			c += solve(n)
		count[root] = c + 1
	else:
		count[root] = 1
	return count[root]

def foo(node):
	if node in count:
		for n in tree[node]:
			foo(n)
		del count[node]
	return

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		i = 0
		d = {}
		while i < n:
			c = 1
			x = s[i]
			i += 1
			while i < n and s[i] == x:
				i += 1
				c += 1
			if x not in d:
				d[x] = []
			d[x].append(c)
		for i in d:
			d[i].sort(reverse=True)
			for x in range(n + 1 - len(d[i])):
				d[i].append(0)
			for j in range(1, len(d[i])):
				d[i][j] += d[i][j - 1]
		ans = [0 for i in range(n + 1)]
		for i in d:
			for x in range(len(d[i])):
				ans[x] = max(ans[x], d[i][x])
		print(*ans)
	return
input = stdin.readline
setrecursionlimit(10 ** 6)
main()


T = int(input())
for _ in range(T):
	N = int(input())
	A = input()
	L = []
	l = A[0]
	for i in range(1, N):
		if A[i - 1] == A[i]:
			l += A[i]
		else:
			L.append(l)
			l = A[i]
	if len(l) > 0:
		L.append(l)
	L.sort(key=lambda x: len(x), reverse=True)
	hast = {}
	for i in L:
		if i[0] in hast:
			hast[i[0]].append(len(i) + hast[i[0]][-1])
		else:
			hast[i[0]] = [len(i)]
	res = []
	for i in range(N):
		maxc = 0
		for j in hast:
			if i > len(hast[j]) - 1:
				maxc = max(maxc, hast[j][-1])
				continue
			maxc = max(maxc, hast[j][i])
		res.append(str(maxc))
	res.append(str(maxc))
	print(' '.join(res))


def func1(temp, p):
	result = -1
	for i in temp:
		if p < len(i) and result < i[p]:
			result = i[p]
	return result

def func(l, letter):
	result = []
	count = 1
	for i in range(len(l)):
		if l[i] == letter and l[i] == l[i + 1]:
			count += 1
		elif l[i] == letter and l[i] != l[i + 1]:
			result.append(count)
			count = 1
		elif l[i] == ' ':
			break
	result.sort(reverse=True)
	return result

def solve():
	n = int(input())
	l = input()
	d = dict()
	for i in l:
		d[i] = d.get(i, 0) + 1
	for i in d:
		d[i] = func(l + ' ', i)
	for i in d:
		for j in range(1, len(d[i])):
			d[i][j] += d[i][j - 1]
	temp = []
	for i in d:
		temp.append(d[i])
	abc = max((len(i) for i in temp))
	count = func1(temp, 0)
	p = 1
	for i in range(n + 1):
		print(count, end=' ')
		if p < abc:
			count = max(count, func1(temp, p))
			p += 1
	print()
t = int(input())
while t:
	solve()
	t -= 1


t = int(input())
for e in range(t):
	n = int(input())
	s = input()
	h = {}
	le = s[0]
	c = 1
	for i in range(1, len(s)):
		if s[i] != le:
			if le in h:
				h[le].append([c, i - c])
			else:
				h[le] = [[c, i - c]]
			le = s[i]
			c = 1
		else:
			c = c + 1
	if le in h:
		h[le].append([c, len(s) - c])
	else:
		h[le] = [[c, len(s) - c]]
	ans = []
	for k in h:
		h[k].sort(reverse=True)
		for i in range(len(h[k])):
			if i == 0:
				h[k][i][0] = h[k][i][0] + 0
			else:
				cn = h[k][i][0]
				h[k][i][0] = h[k][i - 1][0] + cn
	for i in range(n + 1):
		cnt = i
		mx = 0
		for k in h:
			if i >= len(h[k]):
				mx = max(mx, h[k][len(h[k]) - 1][0])
			else:
				mx = max(mx, h[k][i][0])
		ans.append(mx)
	print(*ans)


T = int(input())
for ts in range(T):
	N = int(input())
	A = input()
	if N == 1:
		print(1, 1)
	else:
		l = dict()
		longest = 0
		current = A[0]
		current_long = 1
		for i in range(1, N):
			if A[i] == current and i < N - 1:
				current_long += 1
			elif A[i] == current and i == N - 1:
				current_long += 1
				if current not in l.keys():
					l[current] = [current_long]
				else:
					l[current].append(current_long)
				current = A[i]
				current_long = 1
			elif i == N - 1:
				if current not in l.keys():
					l[current] = [current_long]
				else:
					l[current].append(current_long)
				if A[N - 1] not in l.keys():
					l[A[N - 1]] = [1]
				else:
					l[A[N - 1]].append(1)
			else:
				if current not in l.keys():
					l[current] = [current_long]
				else:
					l[current].append(current_long)
				current = A[i]
				current_long = 1
		for let in l.keys():
			l[let].sort(reverse=True)
		m = dict()
		for let in l.keys():
			m[let] = [l[let][0]]
			for i in range(1, N + 1):
				if i >= len(l[let]):
					m[let].append(m[let][i - 1])
				else:
					m[let].append(m[let][i - 1] + l[let][i])
		ans = [0] * (N + 1)
		for i in range(N + 1):
			curr_ans = 0
			for letter in l.keys():
				curr_ans = max(curr_ans, m[letter][i])
			ans[i] = curr_ans
		print(' '.join(map(str, ans)))


T = int(input())
for _ in range(T):
	n = int(input())
	s = list(input())
	dic = {}
	count = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			count += 1
		else:
			if s[i - 1] in dic.keys():
				dic[s[i - 1]].append(count)
			else:
				dic[s[i - 1]] = [count]
			count = 1
	if s[-1] in dic.keys():
		dic[s[-1]].append(count)
	else:
		dic[s[-1]] = [count]
	for key in dic.keys():
		dic[key].sort(reverse=True)
		for i in range(1, len(dic[key])):
			dic[key][i] += dic[key][i - 1]
	ans = []
	for i in range(n + 1):
		mx = -1
		for key in dic.keys():
			if len(dic[key]) >= 1 + i:
				mx = max(mx, dic[key][i])
			else:
				mx = max(mx, dic[key][-1])
		ans.append(mx)
	print(*ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	d = dict()
	for j in range(97, 123):
		d[chr(j)] = []
	count = 1
	pr = s[0]
	for j in range(1, n):
		if s[j] == s[j - 1]:
			count += 1
		else:
			d[pr].append(count)
			pr = s[j]
			count = 1
	d[pr].append(count)
	max_l = 0
	for j in range(97, 123):
		d[chr(j)] = sorted(d[chr(j)], reverse=True)
		max_l = max(max_l, len(d[chr(j)]))
	ans_list = []
	fin_list = []
	for j in range(97, 123):
		try:
			fin_list.append(d[chr(j)][0])
		except:
			fin_list.append(0)
	max_ans = max(fin_list)
	ans_list.append(max_ans)
	for j in range(1, max_l):
		for k in range(97, 123):
			try:
				fin_list[k - ord('a')] += d[chr(k)][j]
			except:
				pass
		max_ans = max(fin_list)
		ans_list.append(max_ans)
	for j in range(max_l, n + 2):
		ans_list.append(max_ans)
	for j in range(0, n):
		print(ans_list[j], end=' ')
	print(ans_list[-1])


for tcase in range(int(input())):
	n = int(input())
	a = input()
	b = [[] for c in range(26)]
	b[ord(a[0]) - ord('a')].append(1)
	for i in range(1, n):
		if a[i] == a[i - 1]:
			b[ord(a[i]) - ord('a')][-1] += 1
		else:
			b[ord(a[i]) - ord('a')].append(1)
	for c in range(26):
		b[c].sort(reverse=True)
		b[c].extend([0] * (n + 1 - len(b[c])))
		for i in range(n):
			b[c][i + 1] += b[c][i]
	ans = [max((b[c][k] for c in range(26))) for k in range(n + 1)]
	print(' '.join(map(str, ans)))


for _ in range(int(input())):
	n = int(input())
	dit = {c: [] for c in range(97, 123)}
	s = input()
	i = 0
	gp = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			gp += 1
		else:
			dit[ord(s[i - 1])].append(gp)
			gp = 1
	dit[ord(s[-1])].append(gp)
	maxx = 0
	for e in dit:
		dit[e].sort()
		dit[e] = dit[e][::-1]
		arr = []
		curr = 0
		for i in range(len(dit[e])):
			curr += dit[e][i]
			arr.append(curr)
		dit[e] = arr
	ans = []
	for i in range(n + 1):
		for e in dit:
			if len(dit[e]) > i:
				maxx = max(maxx, dit[e][i])
		ans.append(maxx)
	print(*ans)


T = int(input())
for i in range(T):
	N = int(input())
	A = str(input())
	dicto = {}
	leng = 1
	for j in range(1, N):
		if A[j - 1] != A[j]:
			try:
				dicto[A[j - 1]].append(leng)
			except:
				dicto[A[j - 1]] = [leng]
			leng = 1
		else:
			leng = leng + 1
	try:
		dicto[A[N - 1]].append(leng)
	except:
		dicto[A[N - 1]] = [leng]
	dicto2 = {}
	for (k, v) in dicto.items():
		dicto[k].sort(reverse=True)
		dicto2[k] = 0
	for j in range(N + 1):
		maxval = 0
		for (k, v) in dicto.items():
			if len(v) > j:
				dicto2[k] = dicto2[k] + v[j]
			if dicto2[k] > maxval:
				maxval = dicto2[k]
		if j == N:
			print(maxval)
		else:
			print(maxval, end=' ')


import sys
import os
import math
from collections import *
import bisect
from heapq import *
from itertools import permutations, combinations
if os.path.exists('input.txt') and os.path.exists('output.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
input = sys.stdin.readline

def lcm(a, b):
	k1 = math.gcd(a, b)
	k2 = a * b
	return k2 // k1

def inp():
	return map(int, input().strip().split(' '))

def lis():
	return list(inp())
mod = 998244353

def prim(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def dfs(adj, vis, u, l):
	vis[u] = 1
	l.add(u)
	for i in adj[u]:
		if vis[i] == 0:
			dfs(adj, vis, i, l)
mod = 10 ** 9 + 7
ma = 1002
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def dfs(i, j, arr, vis, n, m):
	vis[i][j] = 1
	for x in range(4):
		mx = i + dx[x]
		my = j + dy[x]
		if mx >= 0 and mx < n and (my >= 0) and (my < m) and (vis[mx][my] == 0):
			if arr[i][j] >= arr[mx][my]:
				dfs(mx, my, arr, vis, n, m)

def dfs(a, vis, node, c):
	vis[node] = 1
	c[0] += 1
	if vis[a[node]] == 0:
		dfs(a, vis, a[node], c)
mod = 998244353
mod = 10 ** 9 + 7

def finv(p, q):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
ma = 2 * (10 ** 5 + 1)

def update(ind, val, n):
	while ind <= n:
		fenwick[ind] += val
		ind += ind & -ind

def qsum(ind):
	ans = 0
	while ind > 0:
		ans += fenwick[ind]
		ind -= ind & -ind
	return ans
mod = 10 ** 9 + 7

def f(n):
	if n % 4 == 0:
		return n
	if n % 4 == 1:
		return 1
	if n % 4 == 2:
		return n + 1
	return 0

def dfs(node, par, adj, dp, v):
	dp[node] = 1
	for i in adj[node]:
		if i[0] != par:
			dfs(i[0], node, adj, dp, v)
			dp[node] += dp[i[0]]

def dfs1(node, par, adj, dp, v):
	for i in adj[node]:
		if i[0] != par:
			if i[1] == 1:
				v.append(dp[i[0]])
			else:
				dfs1(i[0], node, adj, dp, v)

def solve():
	n = int(input())
	s = input().split()[0]
	s1 = set()
	for i in range(n):
		s1.add(s[i])
	res = [0 for i in range(n + 1)]
	for i in s1:
		j = 0
		v = []
		while j < n:
			key = s[j]
			cnt = 0
			while j < n and s[j] == key:
				cnt += 1
				j += 1
			if key == i:
				v.append(cnt)
		v.sort(reverse=True)
		s2 = 0
		for i in range(len(v)):
			s2 += v[i]
			res[i] = max(res[i], s2)
	for i in range(1, n + 1):
		res[i] = max(res[i], res[i - 1])
	print(*res)
t = int(input())
for _ in range(t):
	solve()


from sys import stdin, stdout
from collections import defaultdict, Counter, deque
import math, heapq, bisect
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	s = input().strip() + '$'
	cnt = 1
	d = defaultdict(list)
	for i in range(n):
		if s[i] == s[i + 1]:
			cnt += 1
		else:
			d[s[i]].append(cnt)
			cnt = 1
	arr = list()
	for key in d:
		d[key] = sorted(d[key], reverse=True)
		length = len(d[key])
		for i in range(1, length):
			d[key][i] += d[key][i - 1]
		arr.append(d[key])
	np = len(arr)
	res = list()
	maxi = 0
	for k in range(n + 1):
		for j in range(np):
			if k < len(arr[j]):
				maxi = max(maxi, arr[j][k])
		res.append(maxi)
	print(*res)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	s = s + '$'
	cnt = 1
	alphabet = [[] for _ in range(26)]
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			cnt += 1
		else:
			alphabet[ord(s[i - 1]) - ord('a')].append(cnt)
			cnt = 1
	for i in range(26):
		alphabet[i].sort(reverse=True)
		for j in range(1, len(alphabet[i])):
			alphabet[i][j] += alphabet[i][j - 1]
	ans = []
	for i in range(n + 1):
		curr = 0
		for j in range(26):
			if alphabet[j] and i >= len(alphabet[j]):
				curr = max(curr, alphabet[j][-1])
			elif alphabet[j]:
				curr = max(curr, alphabet[j][i])
		ans.append(curr)
	print(*ans)