原文链接: https://leetcode-cn.com/problems/longest-palindrome

英文原文

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome here.

 

Example 1:

Input: s = "abccccdd"
Output: 7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2:

Input: s = "a"
Output: 1

Example 3:

Input: s = "bb"
Output: 2

 

Constraints:

• 1 <= s.length <= 2000
• s consists of lowercase and/or uppercase English letters only.

中文题目

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

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

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

示例 1:

输入:
"abccccdd"

输出:
7

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

通过代码

高赞题解

UPDATE: 米娜桑下午好～～ 刚刚我在公众号【甜姨的奇妙冒险】更新了本题更详细的题解，很多小tips等你来取嗷～～，欢迎大家围观❤️

—–s

🙋今日打卡因为写了2种风格的代码所以慢了点
这题其实是构造性的题目，所以只需要尽可能的左右对称地构造字符串就行了，所以回文串里每种字符都出现了偶数次，除了奇数长度的回文串的时候最中间的那个字符可以出现奇数次。
比如回文串 abba，每个字符都出现了偶数次。而奇数长度的回文串abcbcbcba，c出现了奇数次。

先是利用int数组计数的方法：

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

      int ans = 0;
      for (int x: cnt) {
        // 字符出现的次数最多用偶数次。
        ans += x - (x & 1);
      }
      // 如果最终的长度小于原字符串的长度，说明里面某个字符出现了奇数次，那么那个字符可以放在回文串的中间，所以额外再加一。
      return ans < s.length() ? ans + 1 : ans;  
    }
}

然后可以用Java8的流式风格来写，好像是在小数据集上用stream会比较慢，这样写的耗时会长一点。
可以学习下stream的写法~

class Solution {
    public int longestPalindrome(String s) {
      Map<Integer, Integer> count = s.chars().boxed()
            .collect(Collectors.toMap(k -> k, v -> 1, Integer::sum));

      int ans = count.values().stream().mapToInt(i -> i - (i & 1)).sum();
      return ans < s.length() ? ans + 1 : ans;
    }
}

统计信息

通过次数	提交次数	AC比率
101145	181856	55.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
回文排列	简单