💬 Discord
Sign In
NeetCode #79LC-409EasyArrays & Hashing
← Back to All Problems

#79 · #409 · Longest Palindrome(最长回文串)

📌 Problem Statement & Constraints

Given a string s of lowercase and/or uppercase letters, return the length of the longest palindrome that can be built from its letters. Constraints: 1 <= s.length <= 2000.

💡 Core Algorithmic Approaches

  1. A palindrome is built from pairs of characters, plus optionally one single character in the middle.
  2. For each character, take the largest even number not exceeding its frequency: freq // 2 * 2.
  3. If any character has an odd frequency, exactly one leftover character can occupy the centre, adding 1.
  4. Sum the even parts and add 1 if at least one odd frequency exists.

💻 Benchmark Python3 Implementation

class Solution:
    def longestPalindrome(self, s: str) -> int:
        from collections import Counter
        res = 0
        has_odd = False
        for c in Counter(s).values():
            res += c // 2 * 2              # use as many pairs as possible
            if c % 2:
                has_odd = True
        return res + (1 if has_odd else 0)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + k): O(n) to count, then a constant-size scan over the distinct characters.
💾 Space Complexity
O(k) for the counter, k <= 52.

⚠️ Interview Pitfalls & Follow-ups

  • Adding 1 for every odd frequency: only one character can sit in the centre.
  • Returning len(s): that would require every character to pair up, which fails when an odd count exists.
  • Ignoring the case distinction between upper and lower case: Python's Counter is case-sensitive by default, which matches the problem's requirement.
  • Using freq // 2 instead of freq // 2 * 2: the former counts pairs, not characters.