題目描述：
給定一個包含大寫字母和小寫字母的字符串，找到通過這些字母構造成的最長的回文串。

在構造過程中，請注意區分大小寫。比如 “Aa” 不能當做一個回文字符串。

注意:
假設字符串的長度不會超過 1010。

示例 1:
輸入:
“abccccdd”

輸出:
7

解釋:
我們可以構造的最長的回文串是"dccaccd", 它的長度是 7。

思路：我們用哈希表（映射都可以）記錄下每個字符出現的次數。然后有以下幾種情況：

• 如果個數為偶數，因為偶數可以拆到兩邊，所以直接加上偶數個數即可。
• 奇數，如果字符個數為奇數只有一個的話，我們將其放在中間即可。如果大于一個我們就將大的放中間，其余的減去一變成偶數放到兩邊即可。

代碼：

int longestPalindrome(string s) {unordered_map<char,int>key;for(auto ch:s)key[ch]++;int count =0,cnt=0,mid=0;int ans = 0;for(auto it=key.begin();it!=key.end();++it){if(it->second%2) //為奇數{mid = max(mid,it->second); //記錄最大值count++; //個數cnt +=it->second; }if(it->second%2==0) //為偶數ans +=it->second;}if(count==0)return ans;else if(count==1)return ans+cnt;else{ans +=mid;cnt=cnt-mid-1*(count-1); //放到兩邊的是總的減去放到中間的，因//為每一個奇數都要減一，所以還要減去(count-1)return ans+cnt;}}

優化：我們發現如果是奇數的話只要加上其個數減去一即可。有因為在中間的可以不用減我們只要在后邊特判加上一即可。

int longestPalindrome(string s) {map<char,int> count;for(char ch:s)count[ch]++;int res=0;for(auto it:count){if(it.second&1)res+=it.second-1;//加上奇數字符數-1else res+=it.second;//加上偶數字符數}return res<s.size()?res+1:res;//加上一個單字符放在中間}

總結

以上是生活随笔為你收集整理的最长回文串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。