409. Longest Palindrome

Problem

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.

Problem Summary

Given a string containing uppercase and lowercase letters, find the longest palindrome that can be constructed using these letters. During construction, note that it is case sensitive. For example, "Aa" cannot be considered a palindrome. Note: Assume the length of the string will not exceed 1010.

Solution Approach

• Given a string, use the characters in this string to form a palindrome, and ask what the maximum possible length of the palindrome is.
• This is also an easy problem. First count the frequency of each character, then for each character, take 2 whenever possible. If there are fewer than 2 and the currently constructed palindrome has even length (that is, every pair has been matched), you can take 1. The final combination is the longest palindrome.

Code

package leetcode

func longestPalindrome(s string) int {
	counter := make(map[rune]int)
	for _, r := range s {
		counter[r]++
	}
	answer := 0
	for _, v := range counter {
		answer += v / 2 * 2
		if answer%2 == 0 && v%2 == 1 {
			answer++
		}
	}
	return answer
}