Longest Palindrome

Difficulty: Easy | Acceptance: 56.00% | Paid: No Topics: Hash Table, String, Greedy

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, for example, “Aa” is not considered a palindrome here.

• Examples
• Constraints
• Hash Table Approach
• Greedy Set Approach
• Bit Manipulation Approach

Examples

Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.

Input: s = "a"
Output: 1
Explanation: The longest palindrome that can be built is "a", whose length is 1.

Constraints

1 <= s.length <= 2000
s consists of lowercase and/or uppercase English letters only.

Hash Table Approach

Intuition Count the frequency of each character and use the largest even number from each count, plus one odd character for the center if any exists.

Steps

• Create a frequency map of all characters in the string
• For each character, add the largest even number (count // 2 * 2) to the result
• Track if any character has an odd count
• If there’s any odd count, add 1 to place one character in the center

class Solution:
    def longestPalindrome(self, s: str) -> int:
        from collections import Counter
        char_count = Counter(s)
        length = 0
        has_odd = False
        
        for count in char_count.values():
            length += count // 2 * 2
            if count % 2 == 1:
                has_odd = True
        
        if has_odd:
            length += 1
        
        return length

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) since the character set is fixed (52 letters)
• Notes: Uses fixed-size array for efficiency in Java/C++

Greedy Set Approach

Intuition Use a set to track characters with odd counts. When we see a character twice, we can immediately add 2 to the result.

Steps

• Initialize an empty set and result counter
• For each character, if it’s in the set, remove it and add 2 to result
• If not in set, add it
• If set is not empty at the end, add 1 for the center character

class Solution:
    def longestPalindrome(self, s: str) -> int:
        odd_chars = set()
        length = 0
        
        for c in s:
            if c in odd_chars:
                odd_chars.remove(c)
                length += 2
            else:
                odd_chars.add(c)
        
        if odd_chars:
            length += 1
        
        return length

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) since the set can contain at most 52 characters
• Notes: Single pass through the string with immediate pair counting

Bit Manipulation Approach

Intuition Use a bitmask to track which characters have odd counts. Each bit represents a character, toggling on each occurrence.

Steps

• Initialize a 64-bit bitmask
• For each character, toggle its corresponding bit
• If bitmask is 0, all characters have even counts
• Otherwise, subtract the count of set bits from length and add 1 for center

class Solution:
    def longestPalindrome(self, s: str) -> int:
        bitmask = 0
        
        for c in s:
            if 'A' <= c <= 'Z':
                bit = 1 << (ord(c) - ord('A'))
            else:
                bit = 1 << (ord(c) - ord('a') + 26)
            bitmask ^= bit
        
        if bitmask == 0:
            return len(s)
        else:
            return len(s) - bin(bitmask).count('1') + 1

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) using only a single integer variable
• Notes: Most space-efficient but requires bit counting operation