问题描述
小红正在玩一个字母游戏，她有一串由小写字母组成的字符串。她想要通过重新排列这些字母，构造出一个回文字符串。但是，她希望这个回文字符串是所有可能回文串中字典序最小的那个。请你帮助小红完成这个任务。
给定一个字符串 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;
}
运行结果
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/u013741272/article/details/167700664
