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.

https://discuss.leetcode.com/topic/61442/simple-java-solution-in-one-pass

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
这又是一道关于回文字符串的问题，LeetCode上关于回文串的题有十来道呢，也算一个比较重要的知识点。但是这道题确实不算一道难题，给了我们一个字符串，让我们找出可以组成的最长的回文串的长度，由于字符顺序可以打乱，所以问题就转化为了求偶数个字符的个数，我们了解回文串的都知道，回文串主要有两种形式，一个是左右完全对称的，比如noon, 还有一种是以中间字符为中心，左右对称，比如bob，level等，那么我们统计出来所有偶数个字符的出现总和，然后如果有奇数个字符的话，我们取取出其最大偶数，然后最后结果加1即可.

    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;
    }

http://bookshadow.com/weblog/2016/10/02/leetcode-longest-palindrome/

统计每个字母的出现次数：

  若字母出现偶数次，则直接累加至最终结果

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

若存在出现奇数次的字母，将最终结果+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);
            else set.add(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{
                hs.add(s.charAt(i));
            }
        }
        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
解法：回文字符串，其长度可能是奇数也可能是偶数。总长度为偶数时，每个字符都出现过偶数词，也就是说都是2的倍数；总长度为奇数时，会有一个中间字符，位于字符正中间，两边的其他每个字符必须满足偶数个的条件。既然是求出最长回文字符串的长度，理想情况就是为奇数个。
　　之前讲过，计算字符出现的次数，最直接的方法就是使用数组计算每个字符出现的次数，这里字母大小写敏感，那么就要建立稍微大点的数组，并且，计算索引的方法也稍微麻烦一点。另外，为了便于计算总长度，我们不必最后才计算长度，可以每次发现有偶数个相同字符时，就累加长度，并把该字符出现的次数清零。遍历结束后，再检查是否还有其他字符，如果有任意一个，就可以使用它作为中间字符，回文字符串长度就可以再加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;
    }