题目描述
难度分:1600
输入T(≤104)表示T组数据。所有数据的n之和≤105。
每组数据输入n(1≤n≤105)和长为n的字符串s，仅包含小写英文字母。
如果一个字符串中的每个字母的出现次数都相同，我们就称该字符串为平衡字符串。
每次操作，你可以修改一个s[i]。
你需要把s变成平衡字符串。
输出最少要操作多少次，以及修改后的字符串。如果有多个符合要求的字符串，输出任意一个。
输入样例
4
5
hello
10
codeforces
5
eevee
6
appall
输出样例
1
helno
2
codefofced
1
eeeee
0
appall
算法
枚举+构造
这个题实在不难，但是实现起来感觉特别难受，花了很长时间写了如下冗长的代码，今天实在是优化不动了。
思路很简单，由于s串中最多可能有26种字母，并且字母种数t必须还要能整除n才能保证每种字母的频数都相等，因此我们可以枚举这些情况。先枚举出所有可能的字母频数，存入cands数组中。
对于cands中的每个目标频数target，都计算最小操作数。对于目标频数target，一共有t=ntarget种字母，设s中原本的字母种数为sz，分为以下两种情况：
- sz≤t，这时候需要添加s串中原本不存在的字母，先遍历一遍s得到串中原本存在的字母，然后再随便选t−sz种s串中不存在的字母，每种字母的频数都应该是target。
- sz>t，这时候不需要添加额外的字母，只需要用s串中原本的字母即可。对于某个字母种数t，要想操作数达到最小，只需要让s只保留t种频数大小相邻的字母。预处理得到一个二元组“（字母频数，字母）”数组tup，将它按照字母频数排序，用一个长度为t的窗口滑动计算每个窗口的最小操作次数即可。
对于以上每种情况，将t种字母的频数存入到哈希表need中，根据need构造答案就行，构造方法详见代码中的construt函数。
复杂度分析
时间复杂度
对于情况2，每种目标频数target都需要对tup数组进行排序，情况1不需要。但由于tup最长就是26，所以排序的复杂度可以看成是个很大的常数（准确应该是O(Σlog2Σ)，Σ是字符集的大小）。
预处理出以上需要的各个哈希表瓶颈在于遍历s串，时间复杂度为O(n)；而计算出每个目标频数target的最小操作次数只需要遍历这些哈希表，可以看成是常数。构造出一个答案只需要遍历有限几次s串，时间复杂度也大约是O(n)的。综上，整个算法的时间复杂度近似为O(n)。
空间复杂度
算法过程中的哈希表都是字符集大小的空间消耗，本题中字符集大小在最差情况下为26。而构造出一个答案在construc函数中使用了队列来存索引，在最差情况下会消耗O(n)级别的空间。因此，算法整体的额外空间复杂度为O(n+Σ)（其中Σ是字符集的大小）。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
const int N = 100010;
int t, n;
char s[N], ans[N];
unordered_map<char, int> counter, extra;
void construct(unordered_map<char, int>& need, int target, bool flag) {
unordered_map<char, int> cnt;
queue<int> q;
if(flag) {
for(int i = 1; i <= n; i++) {
if(cnt[s[i]] + 1 <= target) {
ans[i] = s[i];
cnt[s[i]]++;
need[s[i]]--;
if(cnt[s[i]] == target) {
need.erase(s[i]);
}
}else {
q.push(i);
}
}
}else {
for(int i = 1; i <= n; i++) {
if(need.find(s[i]) != need.end()) {
if(cnt[s[i]] + 1 <= target) {
ans[i] = s[i];
cnt[s[i]]++;
need[s[i]]--;
if(cnt[s[i]] == target) {
need.erase(s[i]);
}
}else {
q.push(i);
}
}else {
q.push(i);
}
}
}
if(need.empty()) return;
auto it = need.begin();
while(!q.empty()) {
int i = q.front();
q.pop();
if(it != need.end()) {
ans[i] = it->first;
it->second--;
if(it->second == 0) {
it++;
}
}
}
}
int main() {
scanf("%d", &t);
for(int index = 1; index <= t; index++) {
scanf("%d", &n);
scanf("%s", s + 1);
vector<int> cands;
counter.clear();
extra.clear();
for(int freq = 1; freq <= n; freq++) {
counter[s[freq]]++;
if(n % freq == 0 && n / freq <= 26) {
// 每个字母可能的频数
cands.push_back(freq);
}
}
for(char c = 'a'; c <= 'z'; c++) {
if(counter.find(c) == counter.end()) {
extra[c] = 0;
}
}
int min_op = 0x3f3f3f3f;
for(int target: cands) {
int t = n / target; // 最终字符串中该有的字母种数
int sz = counter.size();
unordered_map<char, int> need;
if(sz <= t) {
// 缺字母或刚好
int res = 0;
auto it = extra.begin();
for(auto&[letter, cnt]: counter) {
need[letter] = target;
res += abs(cnt - target);
}
while(need.size() < t) {
need[it->first] = target;
it++;
res += target;
}
res >>= 1;
if(res < min_op) {
construct(need, target, true);
min_op = res;
}
}else {
// 多字母
vector<pair<int, char>> tup;
for(auto&[letter, cnt]: counter) {
tup.push_back({cnt, letter});
}
sort(tup.begin(), tup.end());
int left = -1, right = -1;
for(int l = 0; l < sz; l++) {
int r;
int res = 0;
if(l + t - 1 < sz) {
r = l + t - 1;
int tot = 0;
for(int i = l; i <= r; i++) {
tot += tup[i].first;
res += abs(tup[i].first - target);
}
res += n - tot;
}else {
int tot = 0;
for(int i = l; i < sz; i++) {
tot += tup[i].first;
res += abs(tup[i].first - target);
}
r = t - (sz - l) - 1;
for(int i = 0; i <= r; i++) {
tot += tup[i].first;
res += abs(tup[i].first - target);
}
res += n - tot;
}
res >>= 1;
if(res < min_op) {
min_op = res;
left = l, right = r;
}
}
if(left >= 0 && right >= 0) {
if(left <= right) {
for(int i = left; i <= right; i++) {
need[tup[i].second] = target;
}
}else {
for(int i = left; i < sz; i++) {
need[tup[i].second] = target;
}
for(int i = 0; i <= right; i++) {
need[tup[i].second] = target;
}
}
construct(need, target, false);
}
}
}
printf("%d\n", min_op);
ans[n + 1] = '\0';
puts(ans + 1);
}
return 0;
}
