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

• LinkedIn
• GitHub

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