最少修改字母使字符串变成回文串

解题思路

要将一个字符串变成回文串，可以通过修改其中的一些字母，使得字符串的前半部分和后半部分对称。我们可以将字符串分为前半部分和后半部分，然后分别统计两部分中每个字母出现的次数。如果某个字母在前半部分出现的次数与后半部分出现的次数之和小于字符串长度的一半，那么这个字母就需要修改。

伪代码

1. 读取输入字符串，并初始化一个大小为26的数组'count'，用来统计每个字母出现的次数。
2. 将字符串分为前半部分和后半部分，分别用两个数组'left'和'right'来保存每个字母出现的次数。
3. 遍历前半部分字符串，将每个字母出现的次数加入'left'数组中。
4. 遍历后半部分字符串，将每个字母出现的次数加入'right'数组中。
5. 遍历'count'数组，分别统计每个字母在前半部分和后半部分出现的次数之和，以及需要修改的次数。
6. 将需要修改的字母按照字典序从小到大的顺序修改为对应的字母，同时更新'left'和'right'数组中的值。
7. 将前半部分字符串按照字典序从小到大的顺序输出。
8. 将后半部分字符串按照字典序从大到小的顺序输出。

复杂度分析

该算法需要遍历整个字符串，时间复杂度为O(n)。空间复杂度为O(1)。其中n为字符串长度。

代码实现

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.length();
    vector<int> count(26, 0);
    vector<int> left(26, 0);
    vector<int> right(26, 0);
    for (int i = 0; i < n/2; i++) {
        count[s[i]-'a']++;
        left[s[i]-'a']++;
    }
    for (int i = n/2; i < n; i++) {
        count[s[i]-'a']--;
        right[s[i]-'a']++;
    }
    int modify = 0;
    for (int i = 0; i < 26; i++) {
        if (left[i] + right[i] < n/2) {
            modify += n/2 - (left[i] + right[i]);
            left[i] += n/2 - (left[i] + right[i]);
        }
    }
    string ans;
    for (int i = 0; i < 26; i++) {
        ans += string(left[i], 'a'+i);
    }
    for (int i = 25; i >= 0; i--) {
        ans += string(right[i], 'a'+i);
    }
    cout << ans << endl;
    return 0;
}