Kolya has a string s of length n consisting of lowercase and uppercase Latin letters and digits.

He wants to rearrange the symbols in s and cut it into the minimum number of parts so that each part is a palindrome and all parts have the same lengths. A palindrome is a string which reads the same backward as forward, such as madam or racecar.

Your task is to help Kolya and determine the minimum number of palindromes of equal lengths to cut s into, if it is allowed to rearrange letters in s before cuttings.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 4·10^5) — the length of string s.

The second line contains a string s of length n consisting of lowercase and uppercase Latin letters and digits.


-----Output-----

Print to the first line an integer k — minimum number of palindromes into which you can cut a given string.

Print to the second line k strings — the palindromes themselves. Separate them by a space. You are allowed to print palindromes in arbitrary order. All of them should have the same length.


-----Examples-----
Input
6
aabaac

Output
2
aba aca 
Input
8
0rTrT022

Output
1
02TrrT20 
Input
2
aA

Output
2
a A

Difficulty: MEDIUM_HARD
Tags: String algorithms

Implementation

Complete search
Skill types: Complete search

Starter code:

Solutions:
import sys
import math
from collections import defaultdict, deque

def is_possible(odd, even):
	each = odd * 2
	if even % each == 0:
		return True
	return False
n = int(sys.stdin.readline())
s = sys.stdin.readline()[:-1]
dic = defaultdict(int)
for i in range(n):
	dic[s[i]] += 1
(odd, even) = (0, 0)
for i in dic:
	if dic[i] % 2 != 0:
		odd += 1
		even += dic[i] - 1
	else:
		even += dic[i]
if odd == 0:
	ans = [0 for x in range(even)]
	cnt = 0
	for i in dic:
		while dic[i] > 0:
			ans[cnt] = i
			ans[even - cnt - 1] = i
			cnt += 1
			dic[i] -= 2
	print(1)
	print(''.join((x for x in ans)))
	sys.exit()
while even >= 0:
	if is_possible(odd, even):
		break
	odd += 2
	even -= 2
length = 1 + even // odd
ans = [deque() for _ in range(odd)]
ansb = [[] for _ in range(odd)]
ansa = [[] for _ in range(odd)]
cnt = 0
for i in dic:
	if dic[i] % 2 != 0:
		ans[cnt].append(i)
		dic[i] -= 1
		cnt += 1
for i in dic:
	while dic[i] > 0:
		if cnt >= odd:
			break
		ans[cnt].append(i)
		ans[cnt + 1].append(i)
		cnt += 2
		dic[i] -= 2
	if cnt >= odd:
		break
cnt = 0
for i in dic:
	if dic[i] > 0:
		x = len(ans[cnt])
		while dic[i] > 0:
			ans[cnt].appendleft(i)
			ans[cnt].append(i)
			dic[i] -= 2
			x += 2
			if x < length:
				pass
			else:
				cnt += 1
				if cnt < odd:
					x = len(ans[cnt])
n = len(ans)
l = []
for i in range(n):
	l.append(''.join((x for x in ans[i])))
print(n)
print(*l)


from collections import Counter
n = int(input())
inp = input()
c = Counter(inp)
t = len(list([x for x in list(c.values()) if x % 2 == 1]))
if t == 0:
	temp = sum([[list(c.items())[j][0]] * (list(c.items())[j][1] // 2) for j in range(len(list(c.items())))], [])
	print(1)
	print(''.join(temp) + ''.join(temp[::-1]))
else:
	ones = list()
	for j in range(len(list(c.items()))):
		i = list(c.items())[j]
		if i[1] % 2 == 1:
			c[list(c.keys())[j]] -= 1
			ones.append(i[0])
	others = sum([[list(c.items())[j][0]] * (list(c.items())[j][1] // 2) for j in range(len(list(c.items())))], [])
	while n % t != 0 or n // t % 2 == 0:
		t += 2
		o = others.pop()
		ones.append(o)
		ones.append(o)
	L = n // t
	ans = list()
	ot = 0
	for i in range(t):
		mid = str()
		if L % 2 == 1:
			mid = ones[i]
		ln = L // 2
		ans.append(''.join(others[ot:ot + ln]) + mid + ''.join(others[ot:ot + ln][::-1]))
		ot += ln
	print(t)
	print(' '.join(ans))


def main():
	import collections
	n = int(input())
	s = input()
	alph = collections.Counter(s)
	odd = sum((x & 1 for x in alph.values()))
	dq = collections.deque()
	if odd == 0:
		print(1)
		for (c, x) in alph.items():
			dq.append(c * (x >> 1))
			dq.appendleft(c * (x >> 1))
		print(*dq, sep='')
	else:
		for odd in range(odd, n):
			if (n - odd) % (odd << 1) == 0:
				print(odd)
				odds = [c for (c, x) in alph.items() if x & 1]
				items = list(alph.items())
				while len(odds) != odd:
					for (i, x) in enumerate(items):
						if x[1] > 1:
							items[i] = (x[0], x[1] - 2)
							odds.append(x[0])
							odds.append(x[0])
							break
				req_length = (n - odd) // odd + 1
				cur_length = 0
				while odd > 0:
					if cur_length == 0:
						dq.append(odds[-1])
						cur_length += 1
						odds.pop()
					x = min(items[-1][1] >> 1, req_length - cur_length >> 1)
					dq.append(items[-1][0] * x)
					dq.appendleft(items[-1][0] * x)
					cur_length += x << 1
					if items[-1][1] - (x << 1) <= 1:
						items.pop()
					else:
						items[-1] = (items[-1][0], items[-1][1] - (x << 1))
					if cur_length == req_length:
						print(*dq, sep='', end=' ')
						odd -= 1
						dq.clear()
						cur_length = 0
				print()
				break
		else:
			print(n)
			print(*s)
try:
	while True:
		main()
except EOFError:
	pass


n = int(input())
string = input()
char = []
charPair = []
charImpair = []
for car in string:
	if car not in char:
		z = string.count(car)
		while z > 1:
			charPair.append(car)
			z -= 2
		if z == 1:
			charImpair.append(car)
		char.append(car)
if len(charImpair) == 0:
	String1 = ''
	for x in charPair:
		String1 += x
	if len(charImpair) == 1:
		String1 += charImpair[0]
	for x in charPair[::-1]:
		String1 += x
	print('1')
	print(String1)
else:
	nbPalin = len(charImpair)
	while len(charPair) % nbPalin != 0:
		nbPalin += 2
		charImpair.append(charPair[-1])
		charImpair.append(charPair[-1])
		del charPair[-1]
	lenPalindrome = n / nbPalin
	Palin = []
	for i in range(nbPalin):
		String2 = ''
		indice = i * int((lenPalindrome - 1) / 2)
		for x in charPair[indice:int(indice + (lenPalindrome - 1) / 2)]:
			String2 += x
		String2 += charImpair[i]
		for x in range(indice + int((lenPalindrome - 1) / 2) - 1, indice - 1, -1):
			String2 += charPair[x]
		Palin.append(String2)
	print(nbPalin)
	String3 = ' '.join(Palin)
	print(String3)


import sys
from collections import Counter

def gen(counter, skip):
	for (c, n) in counter:
		has = n // 2
		if skip > has:
			skip -= has
			has = 0
		elif skip > 0:
			has -= skip
			skip = 0
		for i in range(has):
			yield c

def gen_o(counter, take):
	for (c, n) in counter:
		for i in range(n % 2):
			yield c
	for (c, n) in counter:
		has = n // 2 * 2
		if take > has:
			take -= has
		elif take > 0:
			has = take
			take = 0
		for i in range(has):
			yield c
N = int(next(sys.stdin))
s = next(sys.stdin).strip()
c = Counter(s)
even = 0
odd = 0
items = list(c.items())
for (_, n) in items:
	even += n // 2
	odd += n % 2
generator = gen(items, 0)
generator_o = gen_o(items, 0)
odd_c = odd
if odd == 0:
	print(1)
	front = [next(generator) for i in range(len(s) // 2)]
	fs = ''.join(front)
	print(fs + fs[::-1])
else:
	skip = 0
	while even != 0 and even % odd != 0:
		skip += 1
		odd += 2
		even -= 1
	generator = gen(items, skip)
	generator_o = gen_o(items, skip * 2)
	print(odd)
	per = even // odd
	strs = []
	for i in range(odd):
		front = [next(generator) for i in range(per)]
		fs = ''.join(front)
		strs.append(fs + next(generator_o) + fs[::-1])
	print(' '.join(strs))


n = int(input())
s = input()
d = {}
for c in s:
	if c not in d:
		d[c] = 0
	d[c] += 1
odd = []
sum = 0
for key in d:
	if d[key] % 2 == 1:
		odd.append(key)
		d[key] -= 1
	sum += d[key]
if sum // 2 < len(odd):
	print(len(s))
	for c in s:
		print(c + ' ', end='')
	exit(0)
while True:
	if len(odd) == 0 or sum // 2 % len(odd) == 0:
		break
	sum -= 2
	if sum // 2 < len(odd):
		print(len(s))
		for c in s:
			print(c + ' ', end='')
		exit(0)
	for key in d:
		odd.append(key)
		odd.append(key)
		d[key] -= 2
		if d[key] == 0:
			d.pop(key, None)
		break
if len(odd) == 0:
	odd.append('')
even = []
for key in d:
	even += [key] * (d[key] // 2)
l = sum // 2 // len(odd)
print(len(odd))
for i in range(len(odd)):
	s = odd[i]
	for j in range(i * l, (i + 1) * l):
		s = even[j] + s + even[j]
	print(s + ' ', end='')


(mp, a, p) = ({}, [], [])
n = int(input())
for i in input():
	if i in mp:
		mp[i] += 1
	else:
		mp[i] = 1
odd = 0
for i in mp:
	if mp[i] & 1:
		a.append(i)
		mp[i] -= 1
		odd += 1
	if mp[i]:
		p.append(i)
m = max(1, odd)
for i in range(m, n + 1):
	if not n % i:
		d = n // i
		if odd and (not d & 1):
			continue
		print(i)
		for K in range(i - m):
			a.append(p[-1])
			if mp[p[-1]] > 1:
				mp[p[-1]] -= 1
			else:
				p.pop()
		for k in range(i):
			s = ''
			for j in range(d // 2):
				s += p[-1]
				mp[p[-1]] -= 2
				if not mp[p[-1]]:
					p.pop()
			if odd:
				print(s + a.pop() + s[::-1], end=' ')
			else:
				print(s + s[::-1], end=' ')
		return


from collections import Counter
n = int(input())
cnt = Counter(input())
odd = []
even = []
for (s, c) in cnt.items():
	if c % 2 == 1:
		odd.append([s, c])
	else:
		even.append([s, c])
k = max(1, len(odd))
for i in range(k, n + 1):
	h = n // i
	if i * h == n and (not odd and h % 2 == 0 or (odd and h % 2 == 1)):
		k = i
		break
h = n // k
res = []
while len(res) < k:
	if odd:
		(s, c) = odd.pop()
		res.append(s)
		c -= 1
		if c:
			even.append([s, c])
	elif h % 2:
		res.append(even[0][0])
		res.append(even[0][0])
		even[0][1] -= 2
		if not even[0][1]:
			even.pop(0)
	else:
		res.append('')
for i in range(k):
	s = res[i]
	while len(s) < h:
		t = (h - len(s)) // 2
		(a, c) = even[0]
		if c <= 2 * t:
			c //= 2
			s = a * c + s + a * c
			even.pop(0)
		else:
			s = a * t + s + a * t
			even[0][1] -= 2 * t
	res[i] = s
print(len(res))
print(' '.join(res))


n = int(input())
s = list(input())
d = {}
for char in s:
	if char not in list(d.keys()):
		d[char] = 1
	else:
		d[char] += 1
odd = []
even = []
for char in list(d.keys()):
	for i in range(d[char] // 2):
		even.append(char)
		even.append(char)
	for i in range(d[char] % 2):
		odd.append(char)
if len(odd) <= 1:
	x = ''.join([even[i] for i in range(1, len(even), 2)])
	y = ''.join(odd)
	print(1)
	print(x + y + x[::-1])
elif len(even) % len(odd) == 0 and len(even) // len(odd) % 2 == 0 and (len(even) // len(odd) > 0):
	print(len(odd))
	x = []
	ratio = len(even) // len(odd)
	indx = 0
	for i in range(len(odd)):
		tail = ''
		while len(tail) < ratio // 2:
			tail += even[indx]
			indx += 2
		x.append(tail + odd[i] + tail[::-1])
	print(' '.join(x))
else:
	ratio = len(even) // len(odd)
	max_length = 1
	for i in range(1, ratio + 1, 2):
		if (len(even) + len(odd)) % i == 0 and max_length < i:
			max_length = i
	parts = (len(even) + len(odd)) // max_length
	print(parts)
	x = []
	indx = 0
	for i in range(len(odd)):
		tail = ''
		while len(tail) < max_length // 2:
			tail += even[indx]
			indx += 2
		x.append(tail + odd[i] + tail[::-1])
	middle = []
	for i in range(parts - len(odd)):
		middle.append(even.pop())
	for i in range(len(middle)):
		tail = ''
		while len(tail) < max_length // 2:
			tail += even[indx]
			indx += 2
		x.append(tail + middle[i] + tail[::-1])
	print(' '.join(x))


n = int(input())
s = list(input())
lets = {}
for i in s:
	try:
		lets[i] += 1
	except:
		lets[i] = 1
count = 0
centre = []
rest = []
for i in lets.keys():
	if lets[i] % 2:
		centre.append(i)
		count += 1
	rest += [i] * (lets[i] // 2)
if count == 0:
	t = ''
	for i in lets.keys():
		t = i * (lets[i] // 2) + t + i * (lets[i] // 2)
	print(1)
	print(t)
else:
	extra = 0
	while n % count != 0 or n // count % 2 == 0:
		count += 2
		extra += 1
	for i in range(extra):
		centre += [rest.pop()] * 2
	amt = len(rest) // count
	temp = rest.copy()
	rest = ''
	for i in temp:
		rest += i
	print(count)
	print(rest[0:amt] + centre[0] + rest[1 * amt - 1::-1], end=' ')
	for i in range(1, count):
		print(rest[i * amt:(i + 1) * amt] + centre[i] + rest[(i + 1) * amt - 1:i * amt - 1:-1], end=' ')
	print()


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
N = int(input())
S = input()

def split(s, wc, pl, n):
	ans = []
	if pl % 2 == 0:
		if any([x % 2 == 1 for x in wc.values()]):
			return []
		for i in range(0, len(s), pl):
			t = s[i:i + pl]
			ans.append(t[::2] + t[::-1][::2])
		return ans
	mid = [w for (w, c) in wc.items() if c % 2 == 1]
	if len(mid) > n:
		return []
	midindex = 0
	while len(ans) < n:
		t = ''
		u = mid[midindex] if midindex < len(mid) else ''
		midindex += 1
		if not u:
			u = list([w for (w, c) in wc.items() if c > 0])[0]
		wc[u] -= 1
		need = pl - 1
		while need > 0:
			pneed = need
			for (w, c) in [(w, c) for (w, c) in wc.items()]:
				if c > need:
					t += str(w) * (need // 2)
					wc[w] -= need
					need = 0
					break
				elif c > 1:
					c //= 2
					t += str(w) * c
					wc[w] -= c * 2
					need -= c * 2
			if need == pneed:
				return []
		t = t + u + t[::-1]
		if len(t) < pl:
			return []
		ans.append(t)
	return ans
S = ''.join(sorted(list(S)))
WC = collections.Counter(S)
for parts in range(1, N + 1):
	if N % parts == 0:
		wc = {k: v for (k, v) in WC.items()}
		ans = split(S, wc, N // parts, parts)
		if ans:
			print(parts)
			print(' '.join(ans))
			exit(0)