Leecode 409. 最长回文串

简介: Leecode 409. 最长回文串

题目描述:

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

在构造过程中,请注意区分大小写。比如 “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;  
    }
}


相关文章
|
1月前
(剑指offer)05 替换空格-58 II.-左旋转字符串(2021-11-25)
(剑指offer)05 替换空格-58 II.-左旋转字符串(2021-11-25)
24 0
剑指offer-4.替换空格
剑指offer-4.替换空格
34 0
Leecode 5. 最长回文子串
Leecode 5. 最长回文子串
43 1
Leecode 18. 四数之和
Leecode 18. 四数之和
50 0
|
存储 C++
剑指offer 04. 替换空格
剑指offer 04. 替换空格
69 0
Leecode365. 水壶问题
Leecode365. 水壶问题
52 0
|
算法 C++ Python
每日算法系列【LeetCode 386】字典序排数
每日算法系列【LeetCode 386】字典序排数
【leedcode】0005. 最长回文子串
【leedcode】0005. 最长回文子串
44 0
|
算法 Java C++
替换空格(剑指offer 05)
请实现一个函数,把字符串 s 中的每个空格替换成"%20"。
108 0
LeetCode每日一题(4)——字符的最短距离
LeetCode每日一题(4)字符的最短距离 1.题目 2.示例 3.思路 代码