How to solve [leetcode] 409. Find the Longest Palindrome in a String?

本文共计326个文字，预计阅读时间需要2分钟。

描述：给定一个由小写或大写字母组成的字符串，找出可以构建的最长回文串的长度。这里区分大小写，例如，Aa不被视为回文串。

Description

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example “Aa” is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

分析

题目的意思是：可以用该字符串组成的最长回文子串。

• 用hashmap统计字符的频率，然后遍历hash表把词频为偶数加入结果，把词频为奇数-1加入结果，最后我们判断一下是否有奇数，有的化就是res+1，没有的化就是res了。

代码

class Solution {
public:
int longestPalindrome(string s) {
unordered_map<char,int> m;
for(int i=0;i<s.size();i++){
m[s[i]]++;
}
int res=0;
bool mid=false;
for(auto s:m){
if(s.second%2==0){
res+=s.second;
}else if(s.second%2==1){
mid=true;
res+=s.second;
res--;
}
}
return mid ? res+1:res;
}
};

参考文献

[LeetCode] Longest Palindrome 最长回文串