题目描述:
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。
在构造过程中,请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
示例 1:
输入:
“abccccdd”
输出:
7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
解题思想:遇到有提示字符串仅包含小写(或者大写)英文字母的题,都可以试着考虑能不能构造长度为26的每个元素分别代表一个字母的数组,来简化计算
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) { // 字符出现的次数最多用偶数次。 //x与1进行逻辑与运算,如果x是偶数,则x & 1 = 0;如果x是奇数,则x & 1 = 1. ans += x - (x & 1); } // 如果最终的长度小于原字符串的长度,说明里面某个字符出现了奇数次,那么那个字符可以放在回文串的中间,所以额外再加一。 return ans < s.length() ? ans + 1 : ans; } }