Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters. Letters are case sensitive, for example, “Aa” is not considered a palindrome.

Understand

給一個名為s的字串，由大小寫英文字母組成，要使用這些字母排列組合找出最長的回文長度。

題目把A與a視為不同字元

迴文:從最後一個字元到第一個字元的順序 剛好與 從第一個字元到最後一個字元順序 一致

因此，

當某種字母在字串中出現的頻率為偶數，則這些種類的字母可以放進迴文中。

當某種字母在字串中出現的頻率為奇數，則這些種類的字母只能從中抽取一種插入回文中，能放在正中央作為對稱點，如 aacccbb、AbcbA

Happy Case

Edge Case

Match

題目要考的是 Hash Map(字元頻率統計) + 貪心演算法

每種字元只做一次判斷，最終答案由每次的選擇堆疊而成，加上每次判斷皆互不影響，這是貪心演算法的特徵。

透過Hash Map把當下的字串中的所有字元出現頻率都統計出來，在為每種字元頻率值判斷奇偶數

不要嘗試所有組合

Plan

1. 建立length儲存可能的迴文長度
2. 建立旗杆判斷字串中有無奇數頻率的字元
3. 使用字典{} 遍歷s字串的所有字元，取的當下每種字元的頻率值
4. 遍歷字典中的key-value，並判斷value是偶數還是奇數
   • 是奇數:步驟2的旗杆從false變成true，只把當下的字元頻率值-1 變成偶數值加入回文中，後續在遇到奇數，因為已經加過奇數頻率了(true)所以不在加入奇數頻率字元
   • 是偶數:一律加入迴文中
5. 檢查步驟2的旗杆是否為true
   • 是true，則迴文長度 + 1 (因為步驟4-1已經加入奇數頻率值的部分)
   • 是false，則迴文長度不便

Implement

def longestPalindrome(self, s: str) -> int:
    freq = {}
    odd_flag = false

    for char in s:
        freq[char] = freq.get(char, 0) + 1

    length = 0

    for value in freq.values():
        if value % 2 == 0: #整除2
            length += value
        else:
            if not odd_flag:
                odd_flag = true
                length = length + (value - 1)

    if odd_flag:
        length += 1
    return length

dict.get(key, default) 解說

freq.get(char,0)

• 如果char不存在於freq字典中，則回傳預設值0
• 如果char存在於freq字典中，則回傳char在字典中的value

所以freq.get(char, 0) + 1代表 當char不存在於freq字典中，則把char寫入字典中且value設為1

Reviews

Evaluate

如果要回傳迴文，則空間複雜度上升至O(n)