409. Longest Palindrome

The Longest Palindrome problem is a classic interview question that checks whether you can shift from thinking about “finding” palindromes to “building” one using character counts. Many candidates initially try substring-based methods or attempt to construct the palindrome directly, which adds unnecessary complexity and often leads to slow solutions. This problem pushes you to recognize that only frequencies matter, since order is irrelevant when rearrangement is allowed. It’s especially useful for learning how pairing logic and a single-center rule lead to a clean greedy solution.

Problem statement

You’re given a string s containing English letters where uppercase and lowercase are treated as different characters. Your task is to compute the maximum possible length of a palindrome that can be formed by rearranging and using some or all of these letters.

Constraints:

• 1 ≤ s.length ≤ 2000
• s contains only English letters (a–z and A–Z)
• Uppercase and lowercase letters are distinct (e.g., A ≠ a)

Examples

Why trying all possibilities is impractical

A naive approach is to treat it as a construction problem: try every possible subset of characters (or simply start from length n down to 1), and for each chosen multiset of letters, try all permutations of those letters and check whether any permutation forms a palindrome. The first time you find a palindrome, you record that length as the answer. This is correct because it exhaustively explores all ways to pick and arrange letters, but it’s inefficient because subsets are exponential and permutations are factorial, so it becomes infeasible even for small strings.

Optimized approach using Greedy count pairing

A palindrome is symmetric; every character placed on the left must be mirrored by the same character on the right, so characters can only contribute in pairs. If a character appears c times, it can form c // 2 pairs, contributing 2 * (c // 2) characters to the palindrome (the largest even number ≤ c).

The only exception is the center of the palindrome, which does not need a mirrored partner. That means you can place at most one extra character in the middle. So if any character has an odd count (leaving one leftover after using pairs), you can add exactly 1 more character to the total length, but you can’t use more than one odd leftover because a palindrome has only one center position.

Solution steps

1. Count how many times each character appears in s.
2. Initialize length to 0 and a flag has_odd to False.
3. For each character count:
   1. Add the largest even contribution((count // 2) * 2) from that count to length.
   2. If the count is odd, set has_odd to True.
4. If has_odd is True, add 1 to length (one center character).
5. Return length.

1 / 8

Solution implementation

from collections import Counter

def longestPalindrome(s):
    # Count how many times each character appears
    freq = Counter(s)

    length = 0          # Tracks total usable length from symmetric pairs
    has_odd = False     # True if at least one character has an odd frequency

    # For each character count, take as many pairs as possible
    for count in freq.values():
        length += (count // 2) * 2      # Add the largest even number <= count
        if count % 2 == 1:
            has_odd = True              # Remember that we can place one center char

    # If any odd count exists, we can add exactly one character in the center
    if has_odd:
        length += 1

    return length
    
def main():
    test_cases = [
        "abccccdd",     
        "a",            
        "Aa",           
        "aabbcc",       
        "aaabbbbcc"     
    ]

    for i, s in enumerate(test_cases, start=1):
        result = longestPalindrome(s)
        print(f"{i}.\tInput s = {s!r}")
        print(f"\tlongestPalindromeLength = {result}")
        print("-" *70)


if __name__ == "__main__":
    main()

Time complexity

The runtime is O(n)) where n is the length of the string, because we count characters in one pass and then iterate over the distinct characters (at most 52 for English letters). The work scales linearly with input size.

Space complexity

The space complexity is O(1) because the frequency map stores counts for at most 52 characters (A–Z, a–z), i.e., 52 integer counters. Since this bound is fixed and does not grow with input size, the extra space remains constant.

Edge cases

• All characters unique
  • Example: "abc"
  • Why it works: no pairs are available, but has_odd becomes True, so result is 1 (single center character).
• All counts even
  • Example: "aabbcc"
  • Why it works: every character contributes fully in pairs and has_odd stays False, so no extra center is added.
• Multiple odd counts
  • Example: "aaabbbbcc"
  • Why it works: pairs are taken from all counts, and only one odd leftover is used as the center, adding exactly 1.
• Single character
  • Example: "a"
  • Why it works: zero pairs, one odd available → returns 1.
• Case sensitivity matters
  • Example: "Aa"
  • Why it works: A and a are counted separately, producing no pairs, but one odd allows center length 1.

Common pitfalls

• Adding +1 for every odd count: Only one character can be placed in the center. Multiple odds do not mean multiple center placements.
• Forgetting case sensitivity: Treating A and a as the same character changes counts and produces incorrect results.
• Trying to build the palindrome: Constructing an actual palindrome wastes time and adds complexity; the length can be computed directly from counts.
• Using the full odd count instead of the even part: For a count like 5, you can only use 4 symmetrically; the leftover 1 is only usable once overall as the center.