> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/8.data-structure/627longest-palindrome.md).

# 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 exceed`1010`.

**Example**

Given s =`"abccccdd"`return`7`

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

[**Tags**](http://www.lintcode.com/en/problem/longest-palindrome/#tags)

[Hash Table](http://www.lintcode.com/tag/hash-table/) [Amazon](http://www.lintcode.com/tag/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，就是不能组成回文串的字符，因为回文串最多允许一个不成对出现的字符