【字符串】最长回文串

题目

409. 最长回文串

---

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

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

示例 1：

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

示例 2：

输入: s = "a"
输入: 1

示例 3：

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

提示：

• 1 <= s.length <= 2000
• s 只能由小写和/或大写英文字母组成

解题

方法一：记录频次

思路

记录每个字符出现的次数，偶数次的字符全用，奇数次的字符则少用一个，如果有多余的奇数次字符，则中间可以用一个。

代码

class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> frequencies = new HashMap<>();
        for(char ch : s.toCharArray()) {
            frequencies.put(ch, frequencies.getOrDefault(ch, 0) + 1);
        }

        int ans = 0;
        boolean hasOdd = false;
        for (int frequence : frequencies.values()) {
            if ((frequence & 1) == 0) {
                ans += frequence;
            } else {
                ans += frequence - 1;
                if (!hasOdd) {
                    hasOdd = true;
                }
            }
        }

        return hasOdd ? ans + 1 : ans;
    }
}

优化

使用数组记录

class Solution {
    public int longestPalindrome(String s) {
        int[] frequencies = new int[58];
        for(char ch : s.toCharArray()) {
            frequencies[ch - 'A']++;
        }

        int ans = 0;
        for (int frequence : frequencies) {
            ans += frequence - (frequence & 1);
        }

        return ans < s.length() ? ans + 1 : ans;
    }
}

优化

n >> 1 << 1，一个数做右移一位再左移一位，如果它是偶数则保持不变，如果是奇数则二进制最低位没了。

class Solution {
    public int longestPalindrome(String s) {
        int[] frequencies = new int[58];
        for(char ch : s.toCharArray()) {
            frequencies[ch - 'A']++;
        }

        int ans = 0;
        for (int frequence : frequencies) {
            ans += frequence >> 1 << 1;
        }

        return ans < s.length() ? ans + 1 : ans;
    }
}