当前位置：首页 > article >正文

【五一创作】( 字符串) 409. 最长回文串 ——【Leetcode每日一题】

article 2024/11/15 5:51:06

❓ 409. 最长回文串

难度：简单

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

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

示例 1:

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

示例 2:

输入:s = “a”
输出:1

示例 3：

输入:s = “aaaaaccc”
输出:7

提示:

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

💡思路：

法一：定长数组

由于字符串s只包含大写字母和小写字母，而大写字母A ~ Z的对应十进制ASCII码为65 ~ 90；小x写字母a ~ z的对应十进制ASCII码为97 ~ 122，所以可以使用长度为 123 的整型数组来统计每个字符出现的个数：

如果是偶数个字符，则一定可以构造成回文字符串；
如果是奇数个字符，则所有奇数个字符都需要减去1，最后加上一个1。

法二：哈希表

可以使用哈希表，统计每个字符出现的次数：

如果是偶数个字符，则一定可以构造成回文字符串；
如果是奇数个字符，则所有奇数个字符都需要减去1，最后加上一个1。

🍁代码：(Java、C++)

法一：定长数组
Java

class Solution {
    public int longestPalindrome(String s) {
        int[] cnts = new int[123];
        for(char c : s.toCharArray()){
            cnts[c]++;
        }
        int longest = 0;
        int hasOdd = 0;
        for(int cnt : cnts){
            longest += cnt % 2 == 0 ? cnt : cnt - 1;
            if(cnt % 2 != 0) hasOdd = 1;
        }
        return longest + hasOdd;
    }
}

C++

class Solution {
public:
    int longestPalindrome(string s) {
        vector<int> cnts(123);
        for(char c : s){
            cnts[c]++;
        }
        int longest = 0;
        int hasOdd = 0;
        for(int cnt : cnts){
            longest += cnt % 2 == 0 ? cnt : cnt - 1;
            if(cnt % 2 != 0) hasOdd = 1;
        }
        return longest + hasOdd;
    }
};

法二：哈希表
Java

class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> numOfChar = new HashMap<>();
        for(char c : s.toCharArray()){
            numOfChar.put(c, numOfChar.getOrDefault(c, 0) + 1);
        }
        int longest = 0;
        int hasOdd = 0;
        for(char c : numOfChar.keySet()){
            longest += numOfChar.get(c) % 2 == 0 ? numOfChar.get(c) : numOfChar.get(c) - 1;
            if(numOfChar.get(c) % 2 != 0) hasOdd = 1;
        }
        return longest + hasOdd;
    }
}

C++

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> numOfChar;
        for(char c : s){
            numOfChar[c]++;
        }
        int longest = 0;
        int hasOdd = 0;
        for(auto num : numOfChar){
            longest += num.second % 2 == 0 ? num.second : num.second - 1;
            if(num.second % 2 != 0) hasOdd = 1;
        }
        return longest + hasOdd;
    }
};

🚀 运行结果：

在这里插入图片描述

🕔 复杂度分析：

时间复杂度： $O (n)$ ，其中 n 为字符串s的长度。
空间复杂度： $O (S)$ ，其中 S 为字符集大小。法一：我们使用了一个长度为 123 的数组，存储每个字符出现的次数。法二：哈希映射（HashMap）来存储每个字符出现的次数，最多只会存储 52 个键值对。