Skip to main content

409 - Longest Palindrome

Difficulty: Easy | Pattern: Hash Map / Greedy Counting | Company tags: Google, Amazon, Facebook

Problem Statement​

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive — 'Aa' is not a palindrome.

Example 1:

Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome: "dccaccd" using all letters.

Example 2:

Input: s = "a"
Output: 1

Key Insight​

A palindrome can use:

  • Any letter that appears an even number of times (use all of them)
  • Any letter that appears an odd number of times (use count - 1 of it, leaving one out)
  • One letter with an odd count can be placed in the center

So: length = sum of all even counts + sum of (odd_count - 1) for each odd-count letter + 1 (if any odd-count letter exists)

Algorithm Flow​

Solution​

from collections import Counter

def longestPalindrome(s: str) -> int:
    counts = Counter(s)
    length = 0
    has_odd = False
    
    for count in counts.values():
        length += count if count % 2 == 0 else count - 1
        if count % 2 != 0:
            has_odd = True
    
    return length + (1 if has_odd else 0)

One-Liner​

def longestPalindrome(s: str) -> int:
    from collections import Counter
    counts = Counter(s).values()
    length = sum(c - c % 2 for c in counts)  # use all even counts
    return length + (1 if any(c % 2 for c in counts) else 0)

Dry Run​

s = "abccccdd" → Counter: {c:4, d:2, a:1, b:1}

LetterCountEven part usedOdd?
c44No
d22No
a10Yes
b10Yes

length = 4 + 2 + 0 + 0 = 6; has_odd = True → 6 + 1 = 7 ✓

Edge Cases​

  • All same letter (e.g., "aaaa") → 4 (all used)
  • Single char → 1
  • All unique characters → 1 (just a center)
  • Mix of upper/lower (case-sensitive): "Aa" → 1 (each has count 1)

Complexity​

  • Time: O(n)
  • Space: O(1) — at most 52 distinct characters (uppercase + lowercase)

Key Terms​

TermDefinition
Hash map / counterStructure mapping each character to its frequency in the string.
ParityWhether a count is even or odd; determines if all occurrences of a letter can be mirrored.
Greedy countingMaking the locally optimal choice (use all even counts, drop one from each odd count) without backtracking.
Center characterThe single odd-count letter allowed to sit unmatched in the middle of a palindrome.

FAQ​

Q: Can this be solved without extra space (no hash map)? A: Yes, with a 128/52-entry fixed-size array instead of a Counter, giving true O(1) space since the alphabet size is bounded.

Q: What if the input string is empty? A: Counter("") is empty, the loop never runs, has_odd stays False, so the function correctly returns 0.

Q: Does the answer require using every character in the string? A: No — it only needs the length of the longest buildable palindrome, so odd-count leftovers (beyond one) are simply excluded, not rearranged elsewhere.

Q: How would the approach change if the palindrome had to use all characters? A: It wouldn't always be possible; you'd need to check that at most one character has an odd count, otherwise no valid arrangement exists.

Q: Why can more than one letter contribute an odd count to the total but only one can be a center? A: Every extra unit from an odd count breaks the mirror symmetry required by a palindrome, so only exactly one unmatched character can occupy the middle slot.

Quick Revision​

  • Goal: find the length (not the actual string) of the longest palindrome buildable from the given letters.
  • Case-sensitive: 'a' and 'A' are different characters.
  • Count frequency of every character with a hash map/array.
  • Even counts contribute their full value to the answer.
  • Odd counts contribute count - 1 (drop one instance).
  • If any odd count exists, add exactly 1 for a center character.
  • Time complexity O(n), space O(1) since alphabet size is bounded (~52).
  • Edge cases: empty string → 0; all unique chars → 1; all same char → full count.