题目描述
409. 最长回文串
思路
题目不难，就是所有的坑我都踩进去了。
"abccccdd" -> a: 1, b:1, d:2, c:4
我的思路是 偶数个数的直接相加，然后奇数里面选最大的就是答案：2+4+1=7.
但是有些样例过不了，看了别人的解释：
- 如果某字母有偶数个，因为偶数有对称性，可以把它全部用来构造回文串；但如果是奇数个的话，并不是完全不可以用来构建，也不是只能选最长的那个，而是只要砍掉1个，剩下的变成偶数就可以全部计入了
- 但奇数字母里，可以保留1个不砍，把它作为回文串的中心，所以最后还要再加回一个1
- 但是！如果压根没有奇数的情况，这个1也不能随便加，所以还要分情况讨论。用了flag。
代码
class Solution {
public:
int longestPalindrome(string s) {
unordered_map<char, int> m;
for (char c : s) {
m[c]++;
}
int res = 0;
int single = 0;
int flag = false;
for (auto it = m.begin(); it != m.end(); it++) {
if (it->second % 2 == 0) {
res += it->second;
} else {
flag = true;
res = res + it->second - 1;
}
}
return flag ? res + 1 : res;
}
};
