409. Longest Palindrome
Easy
Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome1
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:
/**
* @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
Palindrome A palindrome is a string that reads the same forward and backward. ↩
