題目連結:
題目意譯:
給定一字串 s ,其只由大小寫英文字母組成。回傳這些字母能組成的最長迴文之長度。
字母的大小寫差別視為相異。例如 "Aa" 在此並不算作一個迴文。
限制:
1 ≦ s.length ≦ 2000
s 只由小寫、大寫英文字母組成。
範例測資:
範例 1:
輸入: s = "abccccdd"
輸出: 7
解釋: 一個可以建構出的最長迴文為 "dccaccd",其長度為 7 。
範例 2:
輸入: s = "a"
輸出: 1
範例 3:
輸入: s = "bb"
輸出: 2
解題思維:
統計所有字母的出現次數,接著掃過這些出現次數。
對於每個字母的出現次數 T ,每兩個我們便可以將迴文加長,因此該字母會貢獻 T ÷ 2 取整 × 2 的長度(也就是找不超過 T 的最大偶數)。
接著因為迴文長度可以為奇數,其最中間的字母不需要與其他字元配對。因此,我們可以再掃過一次所有字母的出現次數去找有誰是出現奇數次的。如果有,則迴文長度又可以再 + 1(注意奇數長度迴文只會有一個中心,所以只能加一次)。
上面掃完之後,最後得出的迴文長度即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。