Longest Palindrome

The Longest Palindrome problem looks like it’s about string scanning, but it’s really about understanding the structure of palindromes and managing character frequencies intelligently. Building the longest palindrome isn’t about rearranging characters cleverly—it’s about using as many paired characters as possible and knowing where you can place a single unpaired character.

This is a classic frequency-count problem that appears in interviews to test combinatorial reasoning and efficient counting.

Problem

You are given a string s consisting of uppercase and lowercase letters. Your task:

Return the length of the longest palindrome you can build using the characters of s.

Important details:

• Characters are case-sensitive (“A” and “a” are different).
• You do not have to return the palindrome itself—only the maximum achievable length.
• You may rearrange characters in any order.

Example

Input:

s = "abccccdd"

Output:

7

Explanation:

A palindrome like “dccaccd” or “ccdcdcc” can be built using seven characters.

Four ‘c’s contribute two pairs, one ‘d’ contributes one pair, and one remaining character can sit in the center.

Input:

s = "a"

Output:

1

A single character is already a palindrome.

Input:

s = "Aa"

Output:

1

Because uppercase and lowercase letters are different, you cannot pair “A” with “a”.

Solution

The key is to count how many characters can be used in pairs—and whether you have at least one leftover character to place in the center.

A palindrome has these structural rules:

• All characters except possibly one must appear in even counts.
• Characters with odd counts can still contribute:
  • Use the largest even part (e.g., from a count of 5, you can use 4).
  • At most one leftover single character can go in the center.

Key idea

Walk through the character counts:

• For every character count:
  • Add the largest even portion to the length.
  • Track if you encountered any count that is odd.

After processing all characters:

• If there was at least one odd count, you can place exactly one extra character in the middle, increasing the total length by 1.

This ensures you get the longest possible palindrome.

Why this works

• Palindromes require symmetry, so pairs of characters are the fundamental building block.
• Odd-count characters still contribute—just not all of their characters.
• Only one odd character can occupy the center; additional odd characters must sacrifice one character each.

This greedy approach guarantees the optimal result in a single pass over the frequency counts.

Algorithm outline

1. Count the frequency of each character using a hash map or array.
2. Initialize length = 0 and odd_found = False.
3. For each frequency f:
   • Add f // 2 * 2 to length.
   • If f is odd, set odd_found = True.
4. After the loop:
   • If odd_found is True, add 1 to length.
5. Return length.

Sample implementation (Python)

Alternative solution: using a set

A faster, elegant trick:

• Use a set.
• Add characters as you see them.
• Remove them when a matching pair completes.

Every time a pair completes, increase the result length by 2.

At the end, if the set is not empty, add 1 for the center character.

This runs in \( O(n) \) time with very clean logic.

Interview insight

The Longest Palindrome problem is an excellent test of:

• Frequency counting and reasoning about character parity
• Recognizing structural constraints of palindromes
• Working backwards from combinatorial rules to code
• Avoiding over-engineering—no rearranging or actual palindrome building is needed

Many interview problems boil down to counting and using the results intelligently. This question is a perfect example of how a simple observation—“palindromes need pairs”—leads to an optimal linear-time solution.