题目描述:
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.
给定一个字符串,利用字符串中的字符组成回文,返回最大回文长度。
一开始以为本题是判断字符串存在的最大回文长度,准备使用分治。后来仔细看发现不是,直接使用哈希统计每个字符出现次数即可:
如果为偶数:直接累加。
如果是奇数,判断-1后是否为偶数,如果为偶数,累加这个偶数。
标记是否出现过奇数(放在回文中间,结果累加1)
实现代码:
public class Solution {
public int LongestPalindrome(string s) {
if(string.IsNullOrWhiteSpace(s)){
return 0;
}
var dict = new Dictionary<char, int>();
var len = s.Length;
for (var i = 0;i < len; i++){
if(!dict.ContainsKey(s[i])){
dict.Add(s[i], 1);
}
else{
dict[s[i]] ++;
}
}
int maxLen = 0;
bool hasMid = false;
foreach (var k in dict.Keys){
if(dict[k] % 2 == 0){
maxLen += dict[k];
}else{
hasMid = true;
if(dict[k] - 1 > 1){
maxLen += dict[k] - 1;
}
}
}
if(hasMid){
maxLen ++;
}
return maxLen;
}
}