問(wèn)題：
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.
大意：
給出一個(gè)由小寫或大寫字母組成的字符串捻艳，找到能被其中的字母組成的最長(zhǎng)的回文的長(zhǎng)度。
這是區(qū)分大小寫的髓窜，比如“Aa”就不能認(rèn)為是回文捍岳。
注意：
假設(shè)給出的字符串長(zhǎng)度不會(huì)超過(guò)1010。
例子：輸入：
“abccccdd”
輸出：
7
解釋：
最長(zhǎng)的回文為“dccaccd”哎壳，長(zhǎng)度為7。
思路：
這里回文的意思就是正著和反著都是一樣的字母順序。思路大家都是比較一致的攘滩，先看看字符串有哪些字母以及各自的數(shù)量，把成雙成對(duì)的數(shù)量的字母都挑出來(lái)纸泡，取其能成雙的最大數(shù)量漂问，這樣可以對(duì)稱地放在回文的兩邊，然后看有沒(méi)有落單的字母或者在成雙后還有剩余一個(gè)的字母，有就放在回文最中間蚤假，這樣就是最長(zhǎng)的回文了栏饮，數(shù)量也就出來(lái)了。這里是區(qū)分大小寫的磷仰，所以要分開(kāi)算袍嬉。不過(guò)題目中的1010這個(gè)最長(zhǎng)字符串長(zhǎng)度沒(méi)發(fā)現(xiàn)有什么特別的用處。
代碼（Java）：
public class Solution {
public int longestPalindrome(String s) {
int[] letterNum = new int[26*2];
char[] sArray = s.toCharArray();
for (int i = 0; i < sArray.length; i++) {
if ((sArray[i] - 'a') >= 0) {// 小寫字母
letterNum[(sArray[i] - 'a')]++;
} else {// 大寫字母
letterNum[(sArray[i] - 'A' + 26)]++;
}
}
int result = 0;
boolean hasSingle = false;// 有無(wú)單個(gè)字符的標(biāo)記
boolean hasOdd = false;// 有無(wú)2個(gè)以上奇數(shù)數(shù)量字符的標(biāo)記
for (int i = 0; i < 26*2; i++) {
if (letterNum[i] > 0 && letterNum[i] < 2) hasSingle = true;
if (letterNum[i] > 1) {
result += letterNum[i] / 2 * 2;
if (letterNum[i] % 2 == 1) hasOdd = true;
}
}
result += hasSingle || hasOdd ? 1 : 0;
return result;
}
}
他山之石：
public int longestPalindrome(String s) {
boolean[] map = new boolean[128];
int len = 0;
for (char c : s.toCharArray()) {
map[c] = !map[c]; // flip on each occurrence, false when seen n*2 times
if (!map[c]) len+=2;
}
if (len < s.length()) len++; // if more than len, atleast one single is present
return len;
}
這個(gè)做法其實(shí)思路是一樣的灶平，只是更加精簡(jiǎn)巧妙伺通，boolan數(shù)組初始化時(shí)都是false，128的長(zhǎng)度是為了包含所有ASCII碼逢享，懶得特意去判斷大小寫了罐监，每次遇到一個(gè)字母就將其對(duì)應(yīng)的位置取反，如果出現(xiàn)兩次就會(huì)又變回false瞒爬，那么每出現(xiàn)兩次就可以將回文長(zhǎng)度加2弓柱。最后看加起來(lái)的長(zhǎng)度和原字符串長(zhǎng)度是否相同，不同則說(shuō)明有單個(gè)字符剩余疮鲫，就可以放在回文正中間吆你，跟我的做法比，思路差不多俊犯，代碼卻巧妙多了妇多，厲害呀。
合集：https://github.com/Cloudox/LeetCode-Record
