1. Understanding the Problem

You are given a string s which consists of lowercase or uppercase letters. Your task is to return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, meaning "A" and "a" are not considered the same character.

What is a Palindrome?

A palindrome is a word, phrase, or sequence that reads the same backward as forward (e.g., "racecar" or "noon").

The Core Constraint (The Trap):

Notice the problem asks for the length of the longest palindrome you can build, not the longest palindromic substring already hidden inside s. You can rearrange the characters in any order you like! However, to form a palindrome, every character must be paired symmetrically around the center—with at most one single unique character allowed in the exact middle.

2. The Naive Approach: Generating All Permutations

The most intuitive, brute-force way to solve this would be to generate every possible combination/permutation of the given characters, check if each resulting string forms a valid palindrome, and keep track of the maximum length found.

Trade-off Analysis

While this brute-force logic will mathematically yield the correct answer, it is completely impractical:

• Time Complexity: O(N!) — Generating permutations of a string grows factorially. If the string has 20 characters, your algorithm will crash due to billions of operations.
• Space Complexity: O(N) — Memory is wasted building and storing temporary strings.

3. The Optimal Approach: The Greedy "Pair Counting" Strategy

To pass a senior-level technical interview, we want to achieve an optimal O(N) time complexity. We don't actually need to construct the physical palindrome string; we only need to calculate its maximum possible length!

Think of it like sorting socks out of the laundry. Every time you find a pair of matching letters (e.g., two 'a's), you can immediately place one on the left side of your palindrome and one on the right side. That adds 2 to your total length.

What about leftover single socks? You can pick at most one unpaired character to place in the very center of your palindrome. Any other remaining single characters cannot be used and must be left behind.

4. The Logic Step-by-Step (Hash Set Method)

While you can use a frequency map, using a Hash Set offers an extremely clean, single-pass implementation:

1. Initialize an empty Hash Set to track characters waiting for a match.
2. Initialize a length counter to 0.
3. Iterate through the string: For each character in s:
   • Check if the character is already inside your set.
   • If it is present: You just found a matching pair! Remove the character from the set and add 2 to length.
   • If it is not present: Add the character to the set (it is waiting for a partner).
4. Handle the Odd Center: After processing the entire string, check if the Hash Set is non-empty. If there is at least one character left inside the set, it means we have unpaired characters. We can pick one of them to sit in the center, so we add 1 to length.
5. Return length.

5. Complexity Analysis

• Time Complexity: O(N) — We process each character in the string of length N exactly once. Hash Set insertions and lookups operate in constant O(1) time.
• Space Complexity: O(1) — Since the input only contains uppercase and lowercase English letters, the set can hold at most 52 unique characters regardless of how long the string is. This makes our space complexity strictly constant!

6. Code Implementations

Expand the sections below to see the optimal O(N) "Hash Set" implementations across different languages.

class Solution:
    def longestPalindrome(self, s: str) -> int:
        unpaired_chars = set()
        length = 0
        
        for char in s:
            if char in unpaired_chars:
                # Found a pair! Remove it and add 2 to our length
                unpaired_chars.remove(char)
                length += 2
            else:
                # Waiting for a matching partner
                unpaired_chars.add(char)
                
        # If any single character remains, we can place 1 in the middle
        if unpaired_chars:
            length += 1
            
        return length

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int longestPalindrome(String s) {
        Set<Character> unpairedChars = new HashSet<>();
        int length = 0;
        
        for (char c : s.toCharArray()) {
            if (unpairedChars.contains(c)) {
                // Found a pair! Remove it and add 2 to our length
                unpairedChars.remove(c);
                length += 2;
            } else {
                // Waiting for a matching partner
                unpairedChars.add(c);
            }
        }
        
        // If any character remains, we can place 1 in the center
        if (!unpairedChars.isEmpty()) {
            length += 1;
        }
        
        return length;
    }
}

#include <string>
#include <unordered_set>

class Solution {
public:
    int longestPalindrome(std::string s) {
        std::unordered_set<char> unpairedChars;
        int length = 0;
        
        for (char c : s) {
            if (unpairedChars.count(c)) {
                // Found a pair! Remove it and add 2 to our length
                unpairedChars.erase(c);
                length += 2;
            } else {
                // Waiting for a matching partner
                unpairedChars.insert(c);
            }
        }
        
        // If any character remains, we can place 1 in the center
        if (!unpairedChars.empty()) {
            length += 1;
        }
        
        return length;
    }
};

7. Conclusion: You Are Ready

Congratulations, you have mastered the greedy pair-counting approach for palindromes! The key takeaway from this problem is recognizing when you actually need to build a structure versus when you simply need to count its constituent mathematical rules. By leveraging a Hash Set to track pairs on the fly, you transformed a complex permutation problem into a clean, single-pass O(N) solution. Keep this "greedy pair matching" mental model ready, as it appears in many frequency-based interview questions!