#P0041. 替换到最大

替换到最大

题目描述

给你一个长度为 nn 的仅由小写字母构成的字符串 ss,然后要求您最多执行一次下面的操作:

  • 选择任意两个下标 ii 和 jj ( 1≤i,j≤n1 \le i, j \le n ),然后把 sis_i 的值替换为 sjs_j 的。

你需要最小化最终得到的新字符串 ss 可能的不同排列数 †^\dagger,并求出此时最终得到的新字符串 ss。

†^\dagger 字符串的排列是将字符按任意顺序排列,例如,"bac "是 "abc "的排列,但 "bcc "不是。此外,如果两个排列的各位字符均相同,这两个排列将被视为同一个排列。

输入格式

每组输入包含多个测试用例!

第一行包含测试用例的数量 tt ( 1≤t≤5001 \le t \le 500 )。

每个测试用例的第一行包含一个正整数 nn ( 1≤n≤101 \le n \le 10 ),代表字符串 ss 的长度。

每个测试用例的第二行包含空格隔开的一个长度为 nn 的字符串 ss,数据保证该字符串只包含小写英文字母。

输出格式

对于每个测试用例,输出通过最多一次操作最小化最终得到的新字符串 ss 可能的不同排列数时最终得到的新字符串 ss。如果有多种可能的解,你可以输出任意一个,只要满足题目要求,均会被视为是正确的。不同测试用例的结果之间以空格隔开。

样例 #1

样例输入 #1

6
3
abc
4
xyyx
8
alphabet
1
k
10
aabbccddee
6
ttbddq

样例输出 #1

cbc
yyyx
alphaaet
k
eabbccddee
tttddq

样例 11 解释

在第一个测试用例中,我们可以通过一次操作获得以下字符串:"abc"、"bbc"、"cbc"、"aac"、"acc"、"aba "和 "abb"。

字符串 "abc "有 66 种不同的排列组合:"abc"、"acb"、"bac"、"bca"、"cab "和 "cba"。

字符串 "cbc "有 33 种不同的排列:"bcc"、"cbc "和 "ccb",这是所有可得到的字符串中最少的。

事实上,对于这个测试用例而言,除了 "abc "之外,所有可得到的字符串都有 33 种排列组合,因此其他的一些替换也都可以被视为正确的。