409-最长回文串

daipeng大约 2 分钟

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

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

 

示例 1:

输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
示例 2:

输入:s = "a"
输入:1
示例 3:

输入:s = "bb"
输入: 2

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindrome
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

回文串是指从正着读和反着读都一样的字符串。

上海自来水来自海上
黄山落叶松叶落山黄
云南丽江城江丽南云
西湖垂柳丝柳垂湖西
花莲浣纱女纱浣莲花
山西空悬寺悬空西山
中山在建房建在山中
山西运煤车煤运西山

简单点的:

aba  奇数个字符
abba 偶数个字符

构造这种字符串很简单，我们遍历给定的字符串，当遇到偶数个同样的字符时就给构造的字符串增加两个，最后假如有多余的字符，那么还可以往构造的字符串中心加一个字符。

解法

 public int longestPalindrome2(String s) {
        Set<Character> set = new HashSet<>(); //使用set保存字符
        int res = 0;
        for (char c : s.toCharArray()) {
            if (set.contains(c)) {//如果set中已经有该字符了，说明该字符可以成对
                set.remove(c); //删除该字符
                res += 2; //最终结果增加2
            }else{
                set.add(c);
            }
        }
        if (!set.isEmpty()) { //假如最终还有剩余字符，那么可以在加一个。
            res++;
        }
        return res;
    }

上面的set可以进一步优化，字符时a-z、A-Z共计52个字符，可以使用数组保存。


 public int longestPalindrome3(String s) {
        int res = 0;
        int[] data = new int[52];
        for (char c : s.toCharArray()) {
            int idx = 0;
            if (Character.isUpperCase(c)) {
                idx = c - 'A' + 26;
            }else{
                idx = c - 'a';
            }
            data[idx] += 1;
        }
        for (int datum : data) {
            res += (datum / 2) * 2; //比如a字符时5，那么对于a字符，可以将4个放到构造字符串里。
        }
        boolean hasLeft = Arrays.stream(data).anyMatch(k -> k % 2 == 1);
        return hasLeft ? res + 1 :res;
    }

比第一种解法快1ms

409-最长回文串

# 解法

解法