C语言/数据结构字符串题解：构造字典序最小的回文串——字符频率统计+贪心构造

问题描述

小红正在玩一个字母游戏，她有一串由小写字母组成的字符串。她想要通过重新排列这些字母，构造出一个回文字符串。但是，她希望这个回文字符串是所有可能回文串中字典序最小的那个。请你帮助小红完成这个任务。

给定一个字符串 s，你需要重新排列其中的字母（可以任意调整顺序），构造出一个回文串，并且这个回文串的字典序要尽可能小。如果无法构造回文串，则返回空字符串。

要求：

测试样例

样例1：

输入：s = "aabb" 输出："abba" 解释：可以构造的回文串有 "abba" 和 "baab"，其中 "abba" 的字典序更小。

样例2：

输入：s = "abc" 输出："" 解释：无法构造回文串，因为只有一个 'a'、一个 'b' 和一个 'c'，无法满足回文串的对称性。

样例3：

输入：s = "aabbbcc" 输出："abcbcba" 解释：字符频率为 a:2, b:3, c:2。字典序最小的构造方式：左半部分按字母顺序使用字符得到 "abc"，中间字符使用剩余的 'b'，最终形成回文 "abcbcba"（字典序小于其他可能如 "abbcbba"）。

约束条件

• 1 ≤ s.length ≤ 10^5
• s 仅由小写英文字母组成
• 如果存在多个解，返回字典序最小的那个
• 如果无法构造回文串，返回空字符串

程序代码

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

char* smallestPalindrome(char* s) {

    int n = strlen(s);

    int count[26] = {0};

    // 统计字符频率

    for (int i = 0; i < n; i++) {

        count[s[i] – 'a']++;

    }

    // 检查奇数次的字符个数

    int oddCount = 0;

    int oddChar = -1;

    for (int i = 0; i < 26; i++) {

        if (count[i] % 2 == 1) {

            oddCount++;

            oddChar = i;

        }

    }

    // 超过一个奇数次的字符，无法构成回文

    if (oddCount > 1) {

        char* result = (char*)malloc(1);

        result[0] = '\\0';

        return result;

    }

    // 构造结果

    char* result = (char*)malloc((n + 1) * sizeof(char));

    int idx = 0;

    // 左半部分：按 a~z 顺序，每个字符取 count/2 个

    for (int i = 0; i < 26; i++) {

        int half = count[i] / 2;

        for (int j = 0; j < half; j++) {

            result[idx++] = 'a' + i;

        }

    }

    // 中间字符（如果有）

    if (oddChar != -1) {

        result[idx++] = 'a' + oddChar;

    }

    // 右半部分：左半部分的逆序

    for (int i = idx – 1 – (oddChar != -1 ? 1 : 0); i >= 0; i–) {

        result[idx++] = result[i];

    }

    result[idx] = '\\0';

    return result;

}

int main() {

    char* r1 = smallestPalindrome("aabb");

    char* r2 = smallestPalindrome("abc");

    char* r3 = smallestPalindrome("aabbbcc");

    printf("%s\\n", r1);  // abba

    printf("%s\\n", r2);  // (空)

    printf("%s\\n", r3);  // abcbcba

    free(r1);

    free(r2);

    free(r3);

    return 0;

}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char* smallestPalindrome(char* s) {
int n = strlen(s);
int count[26] = {0};

// 统计字符频率
for (int i = 0; i < n; i++) {
count[s[i] – 'a']++;
}

// 检查奇数次的字符个数
int oddCount = 0;
int oddChar = -1;
for (int i = 0; i < 26; i++) {
if (count[i] % 2 == 1) {
oddCount++;
oddChar = i;
}
}

// 超过一个奇数次的字符，无法构成回文
if (oddCount > 1) {
char* result = (char*)malloc(1);
result[0] = '\\0';
return result;
}

// 构造结果
char* result = (char*)malloc((n + 1) * sizeof(char));
int idx = 0;

// 左半部分：按 a~z 顺序，每个字符取 count/2 个
for (int i = 0; i < 26; i++) {
int half = count[i] / 2;
for (int j = 0; j < half; j++) {
result[idx++] = 'a' + i;
}
}

// 中间字符（如果有）
if (oddChar != -1) {
result[idx++] = 'a' + oddChar;
}

// 右半部分：左半部分的逆序
for (int i = idx – 1 – (oddChar != -1 ? 1 : 0); i >= 0; i–) {
result[idx++] = result[i];
}

result[idx] = '\\0';
return result;
}

int main() {
char* r1 = smallestPalindrome("aabb");
char* r2 = smallestPalindrome("abc");
char* r3 = smallestPalindrome("aabbbcc");

printf("%s\\n", r1); // abba
printf("%s\\n", r2); // (空)
printf("%s\\n", r3); // abcbcba

free(r1);
free(r2);
free(r3);

return 0;
}

运行结果