## Sunday, October 2, 2016

### LeetCode - 409 Longest Palindrome

https://leetcode.com/problems/longest-palindrome/
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.
```
https://discuss.leetcode.com/topic/61338/what-are-the-odds-python-c
I count how many letters appear an odd number of times. Because we can use all letters, except for each odd-count letter we must leave one, except one of them we can use.
http://blog.csdn.net/mebiuw/article/details/52724207
//统计所有的字母，最终等于所有的出现为偶数的次数+所有奇数的次数-（奇数的个数 - 1）,如果没有奇数则不减 public int longestPalindrome(String s) { char chars[] = s.toCharArray(); int lowerCount[] = new int[26]; int upperCount[] = new int[26]; int odds = 0; int n = s.length(); for(int i=0;i<n;i++){ if(chars[i] < 'a') upperCount[chars[i]-'A'] ++; else lowerCount[chars[i] - 'a']++; } for(int i=0;i<26;i++){ if(lowerCount[i]%2==1) odds++; if(upperCount[i]%2==1) odds++; } if(odds == 0) return n; else return n - odds + 1; }

http://www.cnblogs.com/grandyang/p/5931874.html

```    int longestPalindrome(string s) {
int res = 0;
bool mid = false;
unordered_map<char, int> m;
for (char c : s) ++m[c];
for (auto it = m.begin(); it != m.end(); ++it) {
res += it->second;
if (it->second % 2 == 1) {
res -= 1;
mid = true;
}
}
return mid ? res + 1 : res;
}```

若字母出现偶数次，则直接累加至最终结果
若字母出现奇数次，则将其值-1之后累加至最终结果

def longestPalindrome(self, s): """ :type s: str :rtype: int """ ans = odd = 0 cnt = collections.Counter(s) for c in cnt: ans += cnt[c] if cnt[c] % 2 == 1: ans -= 1 odd += 1 return ans + (odd > 0)

https://discuss.leetcode.com/topic/61300/simple-hashset-solution-java/3
``````public int longestPalindrome(String s) {
Set<Character> set = new HashSet<>();
for (char c : s.toCharArray()) {
if (set.contains(c)) set.remove(c);
}

int odd = set.size();
return s.length() - (odd == 0 ? 0 : odd - 1);
}``````
``````public int longestPalindrome(String s) {
if(s==null || s.length()==0) return 0;
HashSet<Character> hs = new HashSet<Character>();
int count = 0;
for(int i=0; i<s.length(); i++){
if(hs.contains(s.charAt(i))){
hs.remove(s.charAt(i));
count++;
}else{
}
}
if(!hs.isEmpty()) return count*2+1;
return count*2;
}``````
https://www.liuchuo.net/archives/3018
int longestPalindrome(string s) {
int hash[256] = {0}, len = 0, flag = 0;
for(int i = 0; i < s.length(); i++)
hash[s[i]]++;
for(int i = 0; i < 256; i++) {
if(hash[i] % 2 == 0) {
len += hash[i];
} else {
len += (hash[i] - 1);
flag = 1;
}
}
return len + flag;
}
https://discuss.leetcode.com/topic/61359/java-solution-simple-and-clear-using-int-26
``````public int longestPalindrome(String s) {
int[] lowercase = new int[26];
int[] uppercase = new int[26];
int res = 0;
for (int i = 0; i < s.length(); i++){
char temp = s.charAt(i);
if (temp >= 97) lowercase[temp-'a']++;
else uppercase[temp-'A']++;
}
for (int i = 0; i < 26; i++){
res+=(lowercase[i]/2)*2;
res+=(uppercase[i]/2)*2;
}
return res == s.length() ? res : res+1;
}``````
https://my.oschina.net/styshoo/blog/781283

之前讲过，计算字符出现的次数，最直接的方法就是使用数组计算每个字符出现的次数，这里字母大小写敏感，那么就要建立稍微大点的数组，并且，计算索引的方法也稍微麻烦一点。另外，为了便于计算总长度，我们不必最后才计算长度，可以每次发现有偶数个相同字符时，就累加长度，并把该字符出现的次数清零。遍历结束后，再检查是否还有其他字符，如果有任意一个，就可以使用它作为中间字符，回文字符串长度就可以再加1了。
这里，我们可以使用Java提供的BitSet类来替代数组，完美的吻合了我们的所有需求。
``````    private int getIndex(char ch) {
return (int)ch >= 'a' ? ch - 'a' + ('Z' - 'A') : ch - 'A';
}

public int longestPalindrome(String s) {
int ret = 0;
BitSet bs = new BitSet(26 * 2);
for (int i = 0; i < s.length(); i++) {
int index = getIndex(s.charAt(i));
bs.set(index, !bs.get(index));
// 如果之为false，说明取反之前是true，则这是第二次遇到该字母了，回文长度+2
if (!bs.get(index)) {
ret += 2;
}
}
// 不为空说明还有字母，可选择一个作为回文字符串的中间字符。
if (!bs.isEmpty()) {
ret += 1;
}

return ret;
}``````