627.Longest Palindrome

1.Description(Easy)

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.

Notice

Assume the length of given string will not exceed1010.

Example

Given s ="abccccdd"return7

One longest palindrome that can be built is"dccaccd", whose length is7.

Tags

Hash Table Amazon

2.Code

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

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

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

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

若存在出现奇数次的字母，将最终结果+1.

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

use a flag to see whether there is odd letter.

 public int longestPalindrome(String s) {
        if(s==null || s.length()==0){
            return 0;
        }
        HashMap<Character,Integer> map=new HashMap<>();
        for(int i=0;i<s.length();i++){
            char current=s.charAt(i);
            if(map.containsKey(current)){
                map.put(current,map.get(current)+1);
            }else{
                map.put(current,1);
            }
        }
        int result=0;
        boolean flag=false;
        for(Map.Entry<Character,Integer> entry:map.entrySet()){
            int count=entry.getValue();
            if(count%2==0){
                result+=count;
            }else{
                result+=(count-1);
                flag=true;
            }
        }
        if(flag){
            result++;
        }
        return result;
    }

上面那种方法是通过哈希表来建立字符串和其出现次数的映射，这里我们可以换一种思路，来找出搜有奇数个的字符，我们采用的方法是使用一个set集合，如果遍历到的字符不在set中，那么就将其加入set，如果已经在set里了，就将其从set中删去，这样遍历完成后set中就是所有出现个数是奇数个的字符了，那么我们最后只要用s的长度减去0和set长度减一之间的较大值即可，为啥这样呢，我们想，如果没有出现个数是奇数个的字符，那么t的长度就是0，减1成了-1，那么s的长度只要减去0即可；如果有奇数个的字符，那么字符个数减1，就是不能组成回文串的字符，因为回文串最多允许一个不成对出现的字符