题目描述

难度分:$1700$

输入$T(\leq 10^5)$表示$T$组数据。所有字符串的长度之和$\leq 10^5$。

每组数据输入长度$\leq 10^5$的字符串$s$，只包含小写字母。

你可以重新排列$s$中的字母。

定义$t = max(s, rev(s))$，其中$rev(s)$为$s$反转后的字符串。

输出字典序最小的$t$。

输入样例

12
a
aab
abb
abc
aabb
aabbb
aaabb
abbb
abbbb
abbcc
eaga
ffcaba

输出样例

a
aba
bab
bca
abba
abbba
ababa
bbab
bbabb
bbcca
agea
acffba

算法

贪心构造

这个贪心策略非常难想，结合样例错了好多次连蒙带猜才过掉。大致的策略是这样，按照字典序从小到大遍历字母的频数：

1. 如果字母$c$的频数是偶数，就将字母$c$平均分配在答案串$t$的两翼。
2. 否则就先留下一个$c$，把剩下偶数个$c$平均分配在答案串$t$的两翼，此时又有两种情况：$(1)$ 如果除了$c$只剩下一种字母$c’$没有填过，就将那个字母$c’$先填在$t$串中间，然后把$c$填在那一段连续$c’$的中间（如果$c’$的频数为奇数，就将$c$填在那段连续$c’$偏右的中间位置）。$(2)$ 否则先将剩下的所有字母按从左往右的顺序在$t$串中间填完，最后一个$c$填在仅剩的那个位置即可。

复杂度分析

时间复杂度

遍历了一遍$s$统计各个字母的频数，然后根据频数表来构造答案串$t$，每往答案串中填一个字母的时间复杂度为$O(1)$（最多就是遍历一遍$26$个字母的频数表才能确定，仍然可以看成一个与字符串长度$n$无关的常数级别操作）。因此，算法整体的时间复杂度为$O(n)$。

空间复杂度

不算输出串的空间，空间瓶颈就在于各字母的频数表，这个表的规模与字符串长度无关，恒定为$26$（实现的时候稍微开大了一点），这仍然可以看成是常数空间，因此算法的额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 30;
int cnt[N];

string solve(string& s) {
    int n = s.size();
    int p = -1, l = 0, r = n - 1;
    string ans;
    ans.resize(n);
    memset(cnt, 0, sizeof(cnt));
    for(char c: s) {
        cnt[c - 'a']++;
    }
    for(int i = 0; i < 26; i++) {
        while(cnt[i] > 1) {
            ans[l++] = ans[r--] = i + 'a', cnt[i] -= 2;
        }
        if(cnt[i] == 1) {
            // 频数为奇数的字母
            p = i;
            break;
        }
    }
    if(~p) {
        if(*max_element(cnt + p + 1, cnt + 26) == r - l) {
            // 后面的字母只剩一种
            for(int i = p + 1; i < 26; i++) {
                while(cnt[i] > 1) {
                    ans[l++] = ans[r--] = i + 'a';
                    cnt[i] -= 2;
                }
            }
        }
        for(int i = p + 1; i < 26; i++) {
            while(cnt[i]--) {
                ans[l++] = i + 'a';
            }
        }
        ans[r--] = p + 'a';
        cnt[p]--;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    string s;
    while(t--) {
        cin >> s;
        cout << solve(s) << endl;
    }
    return 0;
}