#P0041. 替换到最大
替换到最大
题目描述
给你一个长度为 的仅由小写字母构成的字符串 ,然后要求您最多执行一次下面的操作:
- 选择任意两个下标 和 ( ),然后把 的值替换为 的。
你需要最小化最终得到的新字符串 可能的不同排列数 ,并求出此时最终得到的新字符串 。
字符串的排列是将字符按任意顺序排列,例如,"bac "是 "abc "的排列,但 "bcc "不是。此外,如果两个排列的各位字符均相同,这两个排列将被视为同一个排列。
输入格式
每组输入包含多个测试用例!
第一行包含测试用例的数量 ( )。
每个测试用例的第一行包含一个正整数 ( ),代表字符串 的长度。
每个测试用例的第二行包含空格隔开的一个长度为 的字符串 ,数据保证该字符串只包含小写英文字母。
输出格式
对于每个测试用例,输出通过最多一次操作最小化最终得到的新字符串 可能的不同排列数时最终得到的新字符串 。如果有多种可能的解,你可以输出任意一个,只要满足题目要求,均会被视为是正确的。不同测试用例的结果之间以空格隔开。
样例 #1
样例输入 #1
6
3
abc
4
xyyx
8
alphabet
1
k
10
aabbccddee
6
ttbddq
样例输出 #1
cbc
yyyx
alphaaet
k
eabbccddee
tttddq
样例 解释
在第一个测试用例中,我们可以通过一次操作获得以下字符串:"abc"、"bbc"、"cbc"、"aac"、"acc"、"aba "和 "abb"。
字符串 "abc "有 种不同的排列组合:"abc"、"acb"、"bac"、"bca"、"cab "和 "cba"。
字符串 "cbc "有 种不同的排列:"bcc"、"cbc "和 "ccb",这是所有可得到的字符串中最少的。
事实上,对于这个测试用例而言,除了 "abc "之外,所有可得到的字符串都有 种排列组合,因此其他的一些替换也都可以被视为正确的。