題目:
給定一個只包含大小寫字母的字串,找出可以由這些字母組成的最長回文的長度。回文指的是正著讀和倒著讀都一樣的字串。
範例:
輸入: s = "abccccdd"
輸出: 7
解釋: 我們可以構造的最長回文是 "dccaccd",其長度為 7。
題目是要判斷能夠建立最長回文,所以跟判斷是否是回文的解題思路就不太一樣了,
由於回文就是要成對的字母出現,也就是偶數的成對字母,頂多在加上一個中間奇數的字母,
所以我們就可以這樣去判斷,
class Solution {
public:
int longestPalindrome(string s) {
unordered_map<char, int> map;
for (auto c : s) {
map[c]++;
}
int res = 0;
bool hasOdd = false; // 紀錄是否有出現奇數次的字母
for (auto m : map) {
res += m.second / 2;
if (m.second % 2 == 1) {
hasOdd = true;
}
}
return res * 2 + (hasOdd ? 1 : 0);
}
};