最小回文排列的解法

题目描述

给你一个回文字符串 s，返回它的按字典序最小的回文排列。

  • 回文：从前往后和从后往前读都一样。
  • 排列：字符串中所有字符的重排。
  • 字典序：从第一个字符开始比，谁先小谁就小；前面对完都一样，短的更小。（力扣 3517）

解决方法

1. 常见的想法

把所有回文排列都列出来，排个序，取第一个？No，能解决，但是——

给你二十个字符串让你全排列，你不崩溃，计算机也要崩溃了。暴力当然可解，前提是数据量够小。

2. 换个思路：只看一半

既然是回文，左右两半肯定一样，我们只关心一半就行。

那先统计每个字母出现了几次，一个循环搞定。

int cnt[26] = {0};
for (char c : s) cnt[c - 'a']++;
// 遍历 s，把每个字符转成 0~25 的索引，计数

每个字符都至少出现两次？No——出现奇数次的字符只能有一个（它正好放正中间）。比如 ababa：a 出现 3 次，b 出现 2 次，拿一个 a 当中间，剩下两个 a 两个 b。

3. 拼出左半部分

把每个字符频次的一半按字母序拼起来，得到左半部分 half，顺便记下中间那个奇数字符。

string half;
char mid = 0;
for (int i = 0; i < 26; ++i) {
    half.append(cnt[i] / 2, 'a' + i);   // 频次一半个 'a'+i 拼进 half
    if (cnt[i] % 2 == 1) mid = 'a' + i; // 奇数次的那个字符当中间
}

这样 half 天然就是字典序最小的左半部分。

4. 生成右半部分

把 half 反转就是右半部分，回文就拼成了。

string right = half;
reverse(right.begin(), right.end());

if (mid) return half + mid + right; // 有中间字符
return half + right;                // 没有中间字符

完整代码如下

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

class Solution {
public:
    string smallestPalindrome(string s) {
        int cnt[26] = {0};
        for (char c : s) cnt[c - 'a']++;

        string half;
        char mid = 0;
        for (int i = 0; i < 26; ++i) {
            half.append(cnt[i] / 2, 'a' + i);
            if (cnt[i] % 2 == 1) mid = 'a' + i;
        }

        string right = half;
        reverse(right.begin(), right.end());

        if (mid) return half + mid + right;
        return half + right;
    }
};