🔗 🟢 409. Longest Palindrome

tags: `貪心(Greedy)` `雜湊表(Hash Table)` `計數(Counting)`

題意

給定一個由小寫和大寫字母構成的字串 $s$ ，返回透過這些字母構造成的最長的 迴文（Palindrome） 字串的長度。

在構造過程中，請注意區分大小寫。例如 $\text{Aa}$ 不能當做一個迴文字串。

思路：貪心(Greedy) + 計數(Counting)

為了最大化地使用字母構造迴文，需注意到迴文的特性：

迴文的兩側應該是對稱的，所以每個字母必須成對出現。
一個迴文可以有一個中心點，這個中心點可以是一個未成對的字母。
因此，每個出現偶數次的字母都可以完全使用；而出現奇數次的字母也可以使用，只是其中一個字母將會作為中心點。

具體步驟：

計算每個字母出現的次數。
統計每個字母貢獻的對數，即將每個字母出現次數除以 2 取整數部分，並將其加總。
如果出現了奇數次字母，可以保留一個作為中心點。
返回統計的對數乘以 2，再加上是否有中心點的標誌。

在計數(Counting) 的方法上，可以使用雜湊表(Hash Table) ，但由於已知字母只有 52 個，所以也可以使用一個長度為 52 的陣列來計數。

複雜度分析

時間複雜度 $O(n)$ ，其中 $n$ 為字串 $s$ 的長度。
空間複雜度 $O(1)$ 。

class Solution:
    def longestPalindrome(self, s: str) -> int:
        cnt = Counter(s)
        ans = flag = 0
        for v in cnt.values():
            ans += v >> 1
            if v & 1:
                flag = 1
        return (ans << 1) + flag

class Solution {
public:
    int longestPalindrome(string s) {
        int cnt[52] = {0};
        for (char ch: s){
            if ('a' <= ch && ch <= 'z') cnt[ch-'a']++;
            else cnt[ch-'A'+26]++;
        }
        int ans = 0, flag = 0;
        for (int i=0; i<52; ++i){
            ans += cnt[i] >> 1;
            if (cnt[i] & 1) flag = 1;
        }
        return (ans << 1) + flag;
    }
};