Longest Palindrome — Coding Interview Walkthrough
The core approach: Longest Palindrome is solved by counting character frequencies in O(n) time and O(1) space. Sum all even-frequency counts. For each character with an odd frequency, include all but one occurrence. If any odd-frequency character exists, add one to the center — a palindrome can have exactly one character appearing an odd number of times.
Longest Palindrome asks for the length of the longest palindrome you can build from a set of characters. Don’t confuse it with Longest Palindromic Substring — this one is about construction, not search. It tests whether you understand palindrome structure and can derive a greedy rule from first principles.
Already know how to solve Longest Palindrome? Try a Longest Palindrome mock interview on Intervu →
The Problem
Given a string s, return the length of the longest palindrome that can be built with its characters. Letters are case-sensitive.
Example
Input: s = "abccccdd"
Output: 7 — one longest palindrome is "dccaccd" (2 d’s, 4 c’s, 1 a).
What Interviewers Are Actually Testing
| Skill | What Interviewers Observe |
|---|---|
| Palindrome structure | Do you know palindromes are built from pairs + at most one center? |
| Greedy reasoning | Can you derive the rule from first principles? |
| Case sensitivity | Do you treat ‘A’ and ‘a’ as different? |
Step 1: Clarifying Questions
- Case-sensitive? Yes —
'A'and'a'are different. - Can we reorder characters? Yes — we’re building, not finding in-place.
Step 2: The Key Insight
A palindrome is made of pairs plus at most one center character. Each character with an even frequency contributes its full count. Each odd-frequency character contributes count - 1. If any character has an odd frequency, add 1 for the center.
Python Implementation
from collections import Counter
def longestPalindrome(s: str) -> int:
freq = Counter(s)
length = 0
has_odd = False
for count in freq.values():
length += count // 2 * 2
if count % 2 == 1:
has_odd = True
return length + (1 if has_odd else 0)Time & Space Complexity
| Aspect | Complexity |
|---|---|
| Time | O(n) |
| Space | O(k) — k unique characters |
Common Interview Mistakes
- Confusing with Longest Palindromic Substring. This builds a palindrome from characters; that finds one within a string.
- Forgetting case sensitivity.
'A'and'a'are separate entries. - Not adding the center +1. Forgetting the optional center gives
length - 1.
What a Strong Candidate Sounds Like
“A palindrome consists of pairs plus an optional center. For each character, I use
count // 2 * 2— the even portion. If any character had an odd count, I place one in the center. The answer is the sum of all even portions plus 1 if any odd count exists.”
Related Problems to Practice
- Valid Palindrome — Two-pointer palindrome check.
- Longest Palindromic Substring — Finding palindromes in-place.
- Valid Anagram — Same frequency-counting pattern.
Frequently Asked Questions
How does character frequency dictate the Longest Palindrome?
A viable palindrome simply mirrors characters around a central point, meaning every single letter must occur in symmetrical pairs, except for at most one singular center letter. Tracking character frequencies dictates exactly how large the palindrome mirror can expand.
What data structure elegantly tracks character availability for a Palindrome?
While a Hash Map tracking integer frequencies works perfectly, using a bounded Hash Set allows dynamically adding and removing paired letters. At the end of the evaluation phase, any remaining odd letters represent permissible center pivots.
Practice This in a Mock Interview
Start a mock interview for Longest Palindrome on Intervu.
Further reading:
- How to Prepare for a Coding Interview in 2026, the complete roadmap
- Why LeetCode alone isn’t enough, and what to practice instead
- Practice any LeetCode problem as a live mock interview
- The Grind 75 Pathway, a structured study plan with AI practice links
- Browse all walkthroughs on GitHub, condensed solutions with code