【题解】构造回文串

题意

给你一个字符串，你可以将里面的字符改变成任意其他小写字母，要求在最小的更改次数下，使得更改后的串能重排出字典序最小的回文串。现在给你这个串，求修改次数最少重排后的回文串。

题解

改变和重排都不会变化字符串的长度，所以我们先考虑每个字母分别有多少个。为了构造回文串，除了中间字母所对应的字母个数可以为奇数个，其他字母应该都为偶数个。所以我们可以按照字典序先遍历字母，遇到一个奇数的字母其个数加一，我们再从逆字典序往回找，遇到第一个奇数时其个数减一。若字符中最多只有一个为奇数则退出。这样能保证能构造出字典序最小的字符串。那么除了唯一一个奇数字母，我们按顺序输出每个字符个数的二分之一，然后再倒转一下即可。

复杂度

时间复杂度

代码

#include <bits/stdc++.h>
using namespace std;
int vis[26];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(vis, 0, sizeof(vis));
        string str;
        cin>>str;
        int n=str.length();
        for(int i=0; i<n; i++)
            vis[str[i]-'a']++;
        for (int i = 0; i <26; i++)
        {
            if (vis[i]&1)
            {
                for (int j = 25; j >=0; j--)
                {
                    if (i == j)
                        continue;
                    if (vis[j]&1)
                    {
                        vis[j]--;
                        vis[i]++;
                        break;
                    }
                }
            }
        }
        char ch = '#';
        string ans = "";
        for (int i = 0; i < 26; i++)
        {
            if (vis[i] &1)
                ch = char(i + 'a');
            vis[i] /= 2;
            while (vis[i])
            {
                ans+=i + 'a';
                vis[i]--;
            }
        }
        cout << ans;
        if (ch != '#')
        {
            cout << ch ;
        }
        reverse(ans.begin(), ans.end());
        cout << ans << "\n";
    }
    return 0;
}