0409. Longest Palindrome

题目信息

题号:

0409

难度:

Easy

主题:

字符频次、大小写区分、回文构造、最大长度

原题:

LeetCode 0409

重点:

可以重新排列并舍弃字符、每种字符按实例使用、最多一种奇数频次字符提供中心位置

题目重述

给定只包含大小写英文字母的字符串 s,可以从中选择任意字符并重新排列,构造一个回文字符串。返回能够构造出的回文字符串的最大长度,不需要返回具体排列。

s 的长度位于 [1, 2000]。大小写字母视为不同字符,例如 A 和 a 不能互相配对。每个字符实例最多使用一次;回文两侧需要相同字符成对出现,整个回文最多可以有一个未配对字符位于中心。

自建示例

多个奇数频次只能选一个中心:

输入:s = "aaabbbcc"
输出:7
解释:a 和 b 各使用两个,c 使用两个,再从剩余的 a 或 b 中选一个放在中心,总长度为 7。

大小写不能配对:

输入:s = "Aa"
输出:1
解释:A 与 a 是不同字符,无法放在回文两侧,只能任选一个字符作为长度为 1 的回文。

偶数部分全部利用,奇数部分最多留一个中心

回文两侧必须成对使用同一字符,所以每种字符的频次先取最大的偶数部分;若存在任意奇数频次,还可以从其中一种字符拿一个放在中心。其他奇数频次各自多出的一个不能同时放入同一回文,否则中心会不止一个。

大小写使用独立计数槽位,不能把 A 与 a 合并。

C++ 实现

class Solution {
public:
    int longestPalindrome(std::string s) {
        std::array<int, 52> 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)。