#409

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Longest Palindrome

Determine the length of the longest palindrome constructible from a given string using greedy counting and frequency tracking.

hash table string greedy

Problem Statement

Given a string s consisting of uppercase and lowercase letters, compute the length of the longest palindrome that can be built using its characters. Letters are case sensitive, meaning 'A' and 'a' are treated distinctly.

Return the maximum length as an integer. For example, if s = "abccccdd", one longest palindrome is "dccaccd" with length 7. Ensure your solution efficiently handles strings up to 2000 characters using a greedy selection plus invariant validation strategy.

Examples

Example 1

Input: s = "abccccdd"

Output: 7

One longest palindrome that can be built is "dccaccd", whose length is 7.

Example 2

Input: s = "a"

Output: 1

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.

Solution Approach

Count Character Frequencies

Use a hash table to tally occurrences of each letter. This frequency map captures both uppercase and lowercase counts separately, which is crucial for enforcing case sensitivity.

Apply Greedy Inclusion

For each character, add its largest even count to the palindrome length. If a character count is odd and no central character has been used yet, add 1 for the center of the palindrome. This aligns with the greedy choice plus invariant validation pattern.

Aggregate and Return

Sum the contributions from all characters, considering one possible odd central character. Return the total sum as the longest palindrome length. This approach guarantees linear time O(n) and constant extra space O(1) relative to alphabet size.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The solution iterates through the string once to build the frequency map, which is O(n) time. Aggregating counts over a fixed alphabet is O(1) space, since only English letters are tracked, making it efficient for strings up to 2000 characters.

What Interviewers Usually Probe

Interviewer may ask why counting frequencies is sufficient for palindrome length.
They might check if you correctly handle case sensitivity and odd counts.
They may probe alternative approaches and ask why a full sort or permutation is unnecessary.

Common Pitfalls or Variants

Common pitfalls

Forgetting that letters are case sensitive, mixing 'A' and 'a'.
Failing to include a single odd-count character as the palindrome center.
Attempting to build the actual palindrome string rather than just calculating its length, which wastes time.

Follow-up variants

Compute the longest palindrome substring instead of using all letters.
Allow the input string to include digits or special characters requiring extended hash handling.
Return one actual palindrome string rather than just its length.

FAQ

What is the main pattern used in Longest Palindrome?

The problem follows a greedy choice plus invariant validation pattern, where we greedily use even counts and possibly one odd count in the center.

Do uppercase and lowercase letters count the same?

No, letters are case sensitive, so 'A' and 'a' are counted separately in building the palindrome.

Can I just sort the string and pair characters?

Sorting is unnecessary; counting frequencies with a hash table is sufficient and more efficient.

What is the time and space complexity of the optimal approach?

The approach runs in O(n) time and O(1) space, since the frequency map size is fixed to the number of English letters.

How does GhostInterview handle edge cases?

GhostInterview highlights cases with all odd counts and guides how to include one as a central character to maximize palindrome length.

terminal

Solution

Solution 1: Counting

A valid palindrome string can have at most one character that appears an odd number of times, and the rest of the characters appear an even number of times.

1

2

3

4

5

6

class Solution:
    def longestPalindrome(self, s: str) -> int:
        cnt = Counter(s)
        ans = sum(v // 2 * 2 for v in cnt.values())
        ans += int(ans < len(s))
        return ans

Solution 2: Bit Manipulation + Counting

We can use an array or hash table $odd$ to record whether each character in string $s$ appears an odd number of times, and an integer variable $cnt$ to record the number of characters that appear an odd number of times.

1

2

3

4

5

6

class Solution:
    def longestPalindrome(self, s: str) -> int:
        cnt = Counter(s)
        ans = sum(v // 2 * 2 for v in cnt.values())
        ans += int(ans < len(s))
        return ans

Continue Practicing

#763 partition labels #767 reorganize string #1400 construct k palindrome strings