題目網址：https://leetcode.cn/problems/longest-palindrome/

題意：給一只由大、小寫字母所組成的 string s, 返回這些字母所能組成的最長迴文 string 之長度。

須區分大、小寫, 比如 "Aa" 不能當作一個迴文 string。

Solution：

想法：利用 Greedy。在一個迴文 string 中, 最多只有一個 char 能出現奇數次, 其餘的 char 皆須出現偶數次。我們可以將每個 char 使用偶數次, 使得它們根據迴文中心對稱。在這之後, 如果有剩餘的 char，我們可以再從中取出一個, 作為迴文中心。

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> freqs;
        for (const auto& ch : s) {
            ++freqs[ch];
        }

        int res = 0, odd = 0;
        for (const auto& [ch, freq] : freqs) {
            res += freq / 2 * 2; // 取出該 char 偶數的長度
            if (freq & 1) { // 如果該 char 為奇數, 則把 odd 標記為 1
                odd = 1;
            }
        }

        res += odd;

        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷 s
  • space：$O(n)$ ➔ freqs 中的元素個數不超過 n