【数据结构基础_字符串】Leetcode 409.最长回文串

原题链接：Leetcode 409. 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.
1
2
3

Example 2:

Input: s = "a"
Output: 1
Explanation: The longest palindrome that can be built is "a", whose length is 1.
1
2
3

Constraints:

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

---

方法一：模拟

思路：

回文串除了中心（不一定有）左右两边完全对称
因此要组成回文串的话，需要n对字符加一个且仅有一个字符（如果有的话）
那么就用哈希表来记录出现次数
模拟

c++代码：

class Solution {
public:
    int longestPalindrome(string s) {
        // 字符 次数
        unordered_map<char, int> mp;
        int ans = 0;

        // 遍历 如果有一个字符出现了2次, 将ans+1然后次数归零
        for(auto c : s){
            mp[c]++;
            if(mp[c] == 2){
                ans++;
                mp[c] = 0;
            }
        }

        // ans此时需要变为2倍
        ans *= 2;

        // 遇到出现一次的字符, 作为回文数的中心(这样的字符只有一个)
        for(auto p : mp){
            if(p.second == 1){
                ans++;
                break;
            }
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

复杂度分析：

• 时间复杂度：O(n)，需要遍历字符串一次
• 空间复杂度：O(1)，因为大小写字母最多有52个，哈希表的长度最多为52