LeetCode Longest Palindrome

LeetCode Longest Palindrome

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

题意:给定一个字符串,现要从字符串中抽取若干个字符,构成一个回文串,问最长能构成多长的回文串。

回文串有两种形式,偶数型abba和奇数型abcba,所以我们先hash统计每个字符出现的次数,然后对于偶数的字符可以直接全拿来用,对于奇数的字符,减1之后只拿偶数个字符,但是我们最后还可以把减去的那个字符拿回来构成奇数型回文串,但也就只能拿回一个字符,所以要提前做好标记。

完整代码如下:

class Solution {
public:
	int longestPalindrome(string s) {
		unordered_map<char, int> hash;
		for (int i = 0; i < s.size(); ++i) {
			++hash[s[i]];
		}
		int ans = 0;
		int odd = 0;
		unordered_map<char, int>::iterator it = hash.begin();
		while (it != hash.end()) {
			if ((it->second) & 1) {
				odd = 1;
				ans += it->second - 1;
			} else {
				ans += it->second;
			}
			++it;
		}
		return ans + odd;
	}
};

本代码提交AC,用时9MS。

Leave a Reply

Your email address will not be published. Required fields are marked *