Longest Palindrome

Longest Palindrome

What is this problem about?

The Longest Palindrome interview question gives you a string consisting of lowercase and/or uppercase letters. Your goal is to determine the length of the longest palindrome that can be built using those letters. You don't need to return the palindrome itself, just its maximum possible length. Note that the letters are case-sensitive, meaning 'A' and 'a' are considered different characters.

Why is this asked in interviews?

This is a classic entry-level hash map and frequency counting problem. Companies ask it to see if a candidate understands the structural properties of palindromes. It acts as a great filter: candidates who try to generate all permutations to build actual strings will fail spectacularly, while candidates who recognize that palindromes are just about pairing characters will write a $O(N)$ solution in five minutes.

Algorithmic pattern used

This problem relies on the Hash Table / Counting and Greedy patterns. A palindrome reads the same forwards and backwards, which means every character in it must have a matching pair, with the exception of exactly one character that can sit dead in the center. The algorithm is to count the frequencies of all characters. For each character, we add its largest even count to our total. If any character has an odd count, we can use one extra character at the very end to serve as the center of our palindrome.

Example explanation

Suppose the string is "abccccdd". First, we build a frequency map:

• a: 1
• b: 1
• c: 4
• d: 2

We iterate through these frequencies greedily taking pairs:

• a (1): We can take 0 pairs. (Add 0). Wait, it's odd! We note that an odd count exists.
• b (1): We can take 0 pairs. (Add 0). It's odd.
• c (4): We can take all 4. Length = 4.
• d (2): We can take all 2. Length = 4 + 2 = 6.

We have accumulated a length of 6 using matched pairs ("cddcc"). Because we encountered at least one character with an odd frequency (like 'a' or 'b'), we can place one of them in the absolute center. Length = 6 + 1 = 7. The final longest palindrome length is 7 (e.g., "dccaccd").

Common mistakes candidates make

A very common mistake is adding the entire odd frequency to the total but failing to subtract 1 to make it even. For example, if 'e' appears 5 times, you can use 4 of them as pairs! You should add count - (count % 2) to your total. Another mistake is ignoring the case sensitivity, lumping 'A' and 'a' together into the same frequency bucket.

Interview preparation tip

When solving the Longest Palindrome coding problem, the cleanest way to write the logic is to use a Hash Set to track unpaired characters. Iterate through the string: if a character is in the set, remove it and add 2 to your length (you found a pair!). If it's not, add it to the set. At the end, if the set is not empty, add 1 to your length. This single-pass, one-condition logic is incredibly elegant.