0409. Longest Palindrome
========================
题目信息
--------
:题号: 0409
:难度: Easy
:主题: 字符频次、大小写区分、回文构造、最大长度
:原题: `LeetCode 0409 `_
:重点: 可以重新排列并舍弃字符、每种字符按实例使用、最多一种奇数频次字符提供中心位置
题目重述
--------
给定只包含大小写英文字母的字符串 ``s``,可以从中选择任意字符并重新排列,构造一个回文字符串。返回能够构造出的回文字符串的最大长度,不需要返回具体排列。
``s`` 的长度位于 ``[1, 2000]``。大小写字母视为不同字符,例如 ``A`` 和 ``a`` 不能互相配对。每个字符实例最多使用一次;回文两侧需要相同字符成对出现,整个回文最多可以有一个未配对字符位于中心。
自建示例
--------
多个奇数频次只能选一个中心:
.. code-block:: text
输入:s = "aaabbbcc"
输出:7
解释:a 和 b 各使用两个,c 使用两个,再从剩余的 a 或 b 中选一个放在中心,总长度为 7。
大小写不能配对:
.. code-block:: text
输入:s = "Aa"
输出:1
解释:A 与 a 是不同字符,无法放在回文两侧,只能任选一个字符作为长度为 1 的回文。
偶数部分全部利用,奇数部分最多留一个中心
--------------------------------------------
回文两侧必须成对使用同一字符,所以每种字符的频次先取最大的偶数部分;若存在任意奇数频次,还可以从其中一种字符拿一个放在中心。其他奇数频次各自多出的一个不能同时放入同一回文,否则中心会不止一个。
大小写使用独立计数槽位,不能把 ``A`` 与 ``a`` 合并。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int longestPalindrome(std::string s) {
std::array frequency{};
for (char c : s) {
int id = c >= 'a' ? c - 'a' : 26 + c - 'A';
++frequency[id];
}
int length = 0;
bool hasOdd = false;
for (int count : frequency) {
length += count / 2 * 2;
if (count % 2 == 1) hasOdd = true;
}
return length + (hasOdd ? 1 : 0);
}
};
代码分析
--------
每个字符的偶数份额都能放到回文两侧,所有奇数频次只共同贡献一个中心字符;这是最大长度的必要且充分条件。时间复杂度为 ``O(n)``,额外空间为固定的 ``O(1)``。