409. Longest Palindrome

[mah-shamim]

Topics: Hash Table, String, Greedy

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.

Footnotes

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

[mah-shamim]

We can use a hash table to count the occurrences of each character. The key insight here is:

1. Characters that appear an even number of times can fully contribute to the palindrome.
2. Characters that appear an odd number of times can contribute up to the largest even number that is less than or equal to their count. However, you can use one odd character as the center of the palindrome, so we can add 1 to the final length if there's at least one character with an odd count.

Let's implement this solution in PHP: 409. Longest Palindrome

<?php
/**
 * @param String $s
 * @return Integer
 */
function longestPalindrome($s) {
    $charCount = [];
    $length = 0;
    $oddCountFound = false;

    // Count the occurrences of each character
    for ($i = 0; $i < strlen($s); $i++) {
        $char = $s[$i];
        if (!isset($charCount[$char])) {
            $charCount[$char] = 0;
        }
        $charCount[$char]++;
    }

    // Calculate the length of the longest palindrome
    foreach ($charCount as $count) {
        if ($count % 2 == 0) {
            // Add the entire count if it's even
            $length += $count;
        } else {
            // Add the largest even number less than count
            $length += $count - 1;
            $oddCountFound = true;
        }
    }

    // If there was at least one character with an odd count, we can place one in the middle
    if ($oddCountFound) {
        $length += 1;
    }

    return $length;
}

// Example usage:
$solution = new Solution();
echo $solution->longestPalindrome("abccccdd");  // Output: 7
echo $solution->longestPalindrome("a");  // Output: 1
?>

Explanation:

1. Character Counting: We use an associative array $charCount to keep track of the number of occurrences of each character in the string.

2. Calculate the Palindrome Length:

   • We iterate through the count of each character:
     • If the count is even, we add the full count to the palindrome length.
     • If the count is odd, we add the largest even portion ($count - 1) to the palindrome length and mark that we have found an odd count.
   • If there was at least one character with an odd count, we add 1 to the length to account for the middle character of the palindrome.

3. Edge Cases: The solution handles cases with strings of length 1 and mixed case sensitivity.

This approach ensures an optimal solution with a time complexity of O(n), where n is the length of the string s.

[topugit]

Thanks to solve the problem of finding the length of the longest palindrome that can be built using the letters of a given string s

[mah-shamim]

Thanks