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.
Solution:
（看了 Tag 才发现又是 HashMap，一开始的思路还在想用什么查找的办法找到最长的那个Palindrome）
这题我们不关心最长的 Palindrome 是什么，而关心其长度。我们可以通过 HashMap 来统计每个字母出现的次数（一开始打算用长为52的整型数组，误以为大小写字母的 ASCII 是相连的，后来发现并不是，‘A’ = 65 而 ‘a’ = 97）
- 如果一个字符有偶数个，则可以为最长 Palindrome 贡献所有的字符；
- 如果一个字符有奇数个，则可以为最长 Palindrome 贡献所有字符数-1个字符。
- 最长 Palindrome 最中间可以有字符也可以没有字符，取决于是否含有字符数为奇数的字符。中间的字符可以是“字符数为奇数的字符”中的任意一个。
public class Solution
{
public int longestPalindrome(String s)
{
int count = 0;
boolean hasOdd = false;
HashMap<Character, Integer> hm = new HashMap<>();
for(int i = 0; i < s.length(); i++)
{
int newCount = hm.getOrDefault(s.charAt(i), 0);
++newCount;
hm.put(s.charAt(i), newCount);
}
Set keys = hm.keySet();
Iterator it = keys.iterator();
while(it.hasNext())
{
int value = hm.get(it.next());
if(value > 0 && value % 2 == 0)
count += value;
else
{
count += value - 1;
hasOdd = true;
}
}
return count + (hasOdd ? 1 : 0);
}
}
