Medium

题目描述

给你一个回文字符串 s。

返回 s 的字典序最小的回文排列。

示例 1：

输入：s = "z"
输出："z"
解释：
只有一个字符的字符串本身就是字典序最小的回文。

示例 2：

输入：s = "babab"
输出："abbba"
解释：
重新排列 "babab" → "abbba" 得到最小的字典序回文。

示例 3：

输入：s = "daccad"
输出："acddca"
解释：
重新排列 "daccad" → "acddca" 得到最小的字典序回文。

约束条件：

  • 1 <= s.length <= 10^5
  • s 由小写英文字母组成
  • s 保证是回文的

提示：

  • 将回文看作由两个镜像对称的半部分组成
  • 构造一半（使用 s），然后另一半是它的反转，以获得字典序最小的排列

解题思路

这道题要求我们找到给定回文字符串的字典序最小的回文排列。

核心思路：

由于题目保证输入字符串是回文的，我们可以利用回文的对称性质来解决。回文字符串可以分为两部分：左半部分和右半部分（如果长度为奇数，中间还有一个字符）。

解题步骤：

  1. 统计字符频次：首先统计每个字符出现的次数
  2. 构造左半部分：为了得到字典序最小的结果，我们按字典序遍历所有字符，对于每个字符，将其一半数量放入左半部分
  3. 处理中间字符：如果某个字符的出现次数是奇数，那么多出来的一个字符应该放在回文的中心位置
  4. 构造右半部分：右半部分是左半部分的反转

算法优化：

由于我们只需要构造左半部分，然后镜像得到右半部分，时间复杂度可以优化到 O(n)，其中 n 是字符串长度。我们可以直接统计字符频次，然后按字典序构造结果。

这种方法确保了结果的字典序最小，因为我们总是优先放置字典序较小的字符在前面的位置。

代码实现

class Solution {
public:
    string smallestPalindrome(string s) {
        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }
        
        string left = "";
        string middle = "";
        
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                char c = 'a' + i;
                left += string(count[i] / 2, c);
                if (count[i] % 2 == 1) {
                    middle = c;
                }
            }
        }
        
        string right = left;
        reverse(right.begin(), right.end());
        
        return left + middle + right;
    }
};

class Solution:
    def smallestPalindrome(self, s: str) -> str:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        
        left = []
        middle = ""
        
        for i in range(26):
            if count[i] > 0:
                c = chr(i + ord('a'))
                left.append(c * (count[i] // 2))
                if count[i] % 2 == 1:
                    middle = c
        
        left_str = ''.join(left)
        right_str = left_str[::-1]
        
        return left_str + middle + right_str

public class Solution {
    public string SmallestPalindrome(string s) {
        int[] count = new int[26];
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        StringBuilder left = new StringBuilder();
        string middle = "";
        
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                char c = (char)('a' + i);
                left.Append(new string(c, count[i] / 2));
                if (count[i] % 2 == 1) {
                    middle = c.ToString();
                }
            }
        }
        
        StringBuilder right = new StringBuilder();
        for (int i = left.Length - 1; i >= 0; i--) {
            right.Append(left[i]);
        }
        
        return left.ToString() + middle + right.ToString();
    }
}

/**
 * @param {string} s
 * @return {string}
 */
var smallestPalindrome = function(s) {
    const freq = {};
    for (const char of s) {
        freq[char] = (freq[char] || 0) + 1;
    }
    
    const left = [];
    let middle = '';
    
    for (const char of 'abcdefghijklmnopqrstuvwxyz') {
        if (freq[char]) {
            const pairs = Math.floor(freq[char] / 2);
            for (let i = 0; i < pairs; i++) {
                left.push(char);
            }
            if (freq[char] % 2 === 1 && middle === '') {
                middle = char;
            }
        }
    }
    
    return left.join('') + middle + left.reverse().join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次统计频次，构造结果字符串的时间也是 O(n)
空间复杂度O(1)使用固定大小的数组统计字符频次，不考虑结果字符串的空间

相关题目