Code Implementation

class Solution:
    def longestPalindrome(self, s: str) -> int:
        from collections import Counter
        counts = Counter(s)
        length = 0
        odd_found = False
        for count in counts.values():
            if count % 2 == 0:
                length += count
            else:
                length += count - 1
                odd_found = True
        if odd_found:
            length += 1
        return length
      

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> counts;
        for (char c : s) {
            counts[c]++;
        }
        int length = 0;
        bool odd_found = false;
        for (auto it : counts) {
            if (it.second % 2 == 0)
                length += it.second;
            else {
                length += it.second - 1;
                odd_found = true;
            }
        }
        if (odd_found)
            length += 1;
        return length;
    }
};
      

class Solution {
    public int longestPalindrome(String s) {
        int[] counts = new int[128];
        for (char c : s.toCharArray()) {
            counts[c]++;
        }
        int length = 0;
        boolean oddFound = false;
        for (int count : counts) {
            if (count % 2 == 0) {
                length += count;
            } else {
                length += count - 1;
                oddFound = true;
            }
        }
        if (oddFound) {
            length += 1;
        }
        return length;
    }
}
      

var longestPalindrome = function(s) {
    let counts = {};
    for (let c of s) {
        counts[c] = (counts[c] || 0) + 1;
    }
    let length = 0;
    let oddFound = false;
    for (let key in counts) {
        if (counts[key] % 2 === 0) {
            length += counts[key];
        } else {
            length += counts[key] - 1;
            oddFound = true;
        }
    }
    if (oddFound) {
        length += 1;
    }
    return length;
};
      

Problem Description

Given a string s consisting of uppercase and lowercase letters, your task is to find the length of the longest palindrome that can be built using the letters from s. Each letter in s can be used at most as many times as it appears. You do not need to use all the characters, but you cannot reuse any character more than its frequency in s.

The palindrome does not need to be a substring of s; you can rearrange the letters to form it. The answer should be the maximum possible length of such a palindrome.

• Each character can be used at most as many times as it appears in s.
• The solution must return the length, not the palindrome itself.
• There is always at least one valid answer (possibly a single character).

Thought Process

The first instinct might be to try all possible rearrangements of s to see which one forms the longest palindrome, but that would be extremely inefficient for longer strings. Instead, we should think about the properties of palindromes and how character frequencies affect them.

In a palindrome, characters are mirrored around the center. This means that for every character, we need pairs (even counts) to place symmetrically. If a character appears an odd number of times, we can use all but one of them to form pairs, and possibly use a single odd character in the center.

The optimization comes from realizing that we just need to count how many pairs we can make from each character, and if there are any characters with odd counts, we can add one of them in the center for a longer palindrome.

Solution Approach

• Count Character Frequencies: Use a hash map (dictionary) or array to count how many times each character appears in s.
• Sum Even Counts: For each character, if its count is even, all those characters can be used in the palindrome (half on the left, half on the right).
• Handle Odd Counts: If a character appears an odd number of times, use count - 1 of them (which is even) for pairs. Keep track of whether any odd counts were found.
• Place One Odd Character in the Center: If there was at least one character with an odd count, we can place one such character in the center of the palindrome, increasing the length by 1.
• Return the Total Length: The sum of all even counts plus one (if any odd counts exist) is the maximum palindrome length.

We use a hash map (or array for ASCII) for frequency counting because lookups and updates are O(1), making the whole process efficient.

Example Walkthrough

Let's use the input s = "abccccdd".

• Count frequencies: a:1, b:1, c:4, d:2
• For 'c' (4 times): all 4 can be used (even)
• For 'd' (2 times): both can be used (even)
• For 'a' and 'b' (1 time each): can use 0 for pairs, but since they are odd, we can use one of them in the center
• Sum: 4 (c) + 2 (d) = 6; since at least one odd count exists, add 1 for the center
• Total: 6 + 1 = 7

So, the longest palindrome that can be built is of length 7 (e.g., "dccaccd").

Time and Space Complexity

• Brute-Force Approach: Trying all permutations would take O(n!) time, which is infeasible for large strings.
• Optimized Approach: Counting frequencies takes O(n) time, where n is the length of s. Summing the counts is O(1) if the character set is fixed (e.g., ASCII), or O(k) where k is the number of unique characters.
• Space Complexity: O(1) if using a fixed-size array for ASCII; O(k) for a hash map where k is the number of unique characters.

Summary

The key insight is that palindromes are built from pairs of characters, and at most one unpaired character can be placed in the center. By counting character frequencies and using as many pairs as possible, we can efficiently compute the maximum palindrome length. This approach is both simple and elegant, making use of basic data structures and properties of palindromes for optimal performance.