博客

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。

注意

:

假设字符串的长度不会超过 1010。

示例 1

:

输入:
"abccccdd"

输出:
7

解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

回文串长度为偶数时，其每个字符出现次数为偶数，长度为奇数时，除中间字符外，其他字符出现次数也为偶数；所以，要将给定的字符串构造成最长的回文串，只需要统计字符串中出现次数为偶数的字符的出现个数即可（题目中未要求输出回文串），统计完成后，若个数与字符串长度一致，则完成；若个数与字符串长度不一致，则说明剩余字符出现次数为奇数次，则将统计结果加一即可（将出现次数为奇数次的字符放在回文串中间）。

public class LongestPalindrome_409 {
    public int longestPalindrome(String s) {
        int count = 0;
        List<Character> list = new ArrayList<>();
        for (char str : s.toCharArray()) {
            if (list.contains(str)) {
                count += 2;
                list.remove((Character) str); // char 类型会自动转换为 int 类型，从而造成数组越界异常
            } else {
                list.add(str);
            }
        }
        return count == s.length() ? count : ++count;
    }

    @Test
    public void test() {
        String str = "abccccdd";
        int len = longestPalindrome(str);
        System.out.println(len);
    }
}