題目描述:給定一個包含大小寫英文字母的字串 s,找出用這些字母能夠組成的最長迴文字串的長度。注意是「能組成的最長長度」,而非「找出子字串」——我們可以任意排列這些字母。
解題思路:迴文的關鍵性質是:除了正中間那個字元以外,所有字元都必須成對出現(左右對稱)。因此:
舉例:s = "aabbccc",頻率為 a→2, b→2, c→3。偶數部分:a 貢獻 2,b 貢獻 2,c 貢獻 2(3/2=1,×2=2)。共 6。c 有奇數頻率,所以可放一個在中間,答案為 7。
時間複雜度:O(n) — 遍歷字串一次統計頻率(n 為字串長度),再遍歷哈希表一次(最多 52 個不同字元,為常數),整體為線性時間。
空間複雜度:O(1) — 哈希表最多儲存 52 個英文字母的頻率,為常數空間,與輸入長度無關。
1. Create a frequency map for each character in s. 2. Initialize length = 0, hasOdd = false. 3. For each character and its count in the frequency map: a. Add (count / 2) * 2 to length (use all full pairs). b. If count is odd, set hasOdd = true. 4. If hasOdd is true, add 1 to length (place one char in the center). 5. Return length.
使用陣列計數 O(n):由於字元集固定(大小寫英文字母共 52 個),可改用大小為 128 的整數陣列取代哈希表,以字元的 ASCII 值為索引。常數因子更小、cache 友好,實務上比哈希表快,空間同樣為 O(1)。
使用集合(Set)模擬 O(n):維護一個集合,遍歷字串時若字元已在集合中則移除它並將 length 加 2(配成一對),否則加入集合。迴圈結束後若集合非空則 length 加 1。邏輯直覺但需要集合的插入與查找操作,常數略大。