← 返回题目列表

Codeforces · 1781/C

C. 相同频率

中文机器翻译题面 查看原题

如果字符串中出现的所有字符出现相同的次数,我们称该字符串为平衡字符串。例如,“coder”、“appall”和“ttttttt”是平衡的,而“wowwow”和“codeforces”则不是。

给你一个字符串$$$s$$$,长度为$$$n$$$,由小写英文字母组成。找到一个由小写英文字母组成的、长度与 $$$n$$$ 相同的平衡字符串 $$$t$$$,并且在尽可能少的位置上与字符串 $$$s$$$ 不同。换句话说,使得 $$$s_i \ne t_i$$$ 的索引 $$$i$$$ 的数量应该尽可能小。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例由两行组成。第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 字符串 $$$s$$$ 的长度。

第二行包含长度为$$$n$$$的字符串$$$s$$$,由小写英文字母组成。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,打印字符串 $$$s$$$ 和平衡字符串 $$$t$$$ 可以不同的最小位置数,后跟这样的字符串 $$$t$$$。

如果有多个解决方案,请打印其中一个。可以证明,至少有一个平衡弦总是存在的。

示例

输入 #1

4
5
hello
10
codeforces
5
eevee
6
appall

输出 #1

1
helno
2
codefofced
1
eeeee
0
appall

注意

在第一个测试用例中,给定的字符串“hello”不平衡:字母“h”、“e”和“o”在其中出现一次,而字母“l”出现两次。另一方面,字符串“helno”是平衡的:其中存在五个不同的字母,并且每个字母只出现一次。字符串“hello”和“helno”只有一个位置不同:第四个字符。其他解决方案也是可能的。

在第二个测试用例中,字符串“codefofced”是平衡的,因为其中仅存在字母“c”、“o”、“d”、“e”和“f”,并且每个字母都恰好出现两次。

在第三个测试用例中,字符串“eeeee”是平衡的,因为其中只存在字母“e”。

在第四个测试用例中,给定的字符串“appall”已经是平衡的。