409. Longest Palindrome

409. Longest Palindrome

Easy

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.

Example 1:

• Input: s = “abccccdd”
• Output: 7
• Explanation: One longest palindrome that can be built is “dccaccd”, whose length is 7.

Example 2:

• Input: s = “a”
• Output: 1
• Explanation: The longest palindrome that can be built is “a”, whose length is 1.

Constraints:

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

Solution:

class Solution { /** * @param String $s * @return Integer */ function longestPalindrome($s) { $ans = 0; $count = array_fill(0, 128, 0); foreach(str_split($s) as $c) { $count[ord($c)]++; } foreach($count as $freq) { $ans += $freq % 2 == 0 ? $freq : $freq - 1; } $hasOddCount = false; foreach($count as $c) { if($c % 2 != 0) { $hasOddCount = true; break; } } return $ans + ($hasOddCount ? 1 : 0); }
}

Contact Links

1. Palindrome A palindrome is a string that reads the same forward and backward. ↩