LeetCode 409—— 最长回文串

本文主要是介绍LeetCode 409—— 最长回文串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目

2. 解题思路

要想组成回文串，那么只有最中间的字符可以是奇数个，其余字符都必须是偶数个。

所以，我们先遍历一遍字符串，统计出每个字符出现的次数。

然后如果某个字符出现了偶数次，那么回文串长度就增加这个字符出现的次数；如果某个字符出现了奇数次，那么回文串长度也只能增加小于这个奇数次的最大偶数。

最后，如果存在奇数个的字符，那么中间可以放一个奇数字符，回文串长度加 1。

3. 代码实现

class Solution {
public:int longestPalindrome(string s) {vector<int> alphabet_num(54, 0);for (size_t i = 0; i < s.size(); ++i) {int idx = 0;if (s[i] >= 'a' && s[i] <= 'z') {idx = s[i] - 'a';} else if (s[i] >= 'A' && s[i] <= 'Z') {idx = s[i] - 'A' + 26;}alphabet_num[idx]++;}int ret = 0;bool has_odd = false;for (size_t i = 0; i < alphabet_num.size(); ++i) {ret += (alphabet_num[i] / 2) * 2;if (alphabet_num[i] % 2 != 0) {has_odd = true;}}if (has_odd) {ret += 1;}return ret;}
};

这篇关于LeetCode 409—— 最长回文串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---