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)``。