Longest Palindrome (Letters)

Problem

Given a string of letters (case-sensitive), return the length of the longest palindrome you can build using its letters.

Constraints

• 1 ≤ s.length ≤ 2000
• lowercase / uppercase letters

Approach — Hashing & Counting

This is a Hashing & Counting problem. The idea: store what you've seen in a hash map for O(1) lookups, trading a little space to avoid a nested scan. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def longestPalindrome(self, s):
        from collections import Counter
        length = 0
        odd = 0
        for c in Counter(s).values():
            length += c - (c & 1)
            if c & 1:
                odd = 1
        return length + odd

Java

class Solution {
    public int longestPalindrome(String s) {
        int[] counts = new int[128];
        for (char c : s.toCharArray()) counts[c]++;
        int len = 0;
        boolean hasOdd = false;
        for (int c : counts) {
            len += (c / 2) * 2;
            if (c % 2 == 1) hasOdd = true;
        }
        return len + (hasOdd ? 1 : 0);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.