CF1781C Equal Frequencies

我们称一个字符串是平衡的，如果其中所有出现过的字符出现的次数都相同。例如，“coder”、“appall” 和 “ttttttt” 都是平衡的，而 “wowwow” 和 “codeforces” 不是。 给定一个长度为 $n$ 的仅包含小写英文字母的字符串 $s$。请你找到一个长度同为 $n$ 的平衡字符串 $t$，使得 $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$。 如果有多种方案，输出任意一种即可。可以证明至少存在一个平衡字符串。

在第一个测试用例中，给定字符串 “hello” 不是平衡的：字母 'h'、'e' 和 'o' 各出现一次，而字母 'l' 出现了两次。另一方面，字符串 “helno” 是平衡的：其中有五个不同的字母，每个都只出现一次。字符串 “hello” 和 “helno” 仅在第四个字符不同。其他方案也是可以的。 在第二个测试用例中，字符串 “codefofced” 是平衡的，因为只出现了 'c'、'o'、'd'、'e' 和 'f' 这五个字母，并且每个都出现了两次。 在第三个测试用例中，字符串 “eeeee” 是平衡的，因为只出现了字母 'e'。 在第四个测试用例中，给定字符串 “appall” 已经是平衡的。 由 ChatGPT 4.1 翻译