LeetCode 409: Longest Palindrome

Problem Restatement

We are given a string s.

The string contains lowercase and uppercase English letters.

We may rearrange the letters in any order.

Return the length of the longest palindrome that can be built using those letters.

Letters are case-sensitive, so:

"A" != "a"

The problem asks for the length only, not the palindrome itself. The constraints are 1 <= s.length <= 2000, and the string contains lowercase and uppercase English letters only.

Input and Output

Example function shape:

def longestPalindrome(s: str) -> int:
    ...

Examples

Example 1:

s = "abccccdd"

The answer is:

7

One possible palindrome is:

"dccaccd"

Its length is 7.

Character counts:

We can use all 4 copies of c.

We can use all 2 copies of d.

Among a and b, only one can be placed in the center.

So the longest length is:

4 + 2 + 1 = 7

Example 2:

s = "a"

The answer is:

1

A single character is already a palindrome.

First Thought: Build Every Palindrome

A brute force approach would try to rearrange the characters in many possible orders and check which arrangements are palindromes.

This is unnecessary.

We do not need the actual palindrome. We only need its maximum length.

So we only need to know how many times each character appears.

Key Insight

In a palindrome, characters on the left and right sides must form pairs.

For example:

abccba

The left side mirrors the right side.

So every character used on the sides must be used an even number of times.

Only one character may appear an odd number of times, and that character can sit in the center.

Examples:

"racecar"

The character e appears once in the center.

"abccba"

Every character appears an even number of times.

So for each character count:

1. Use the largest even part.
2. If at least one odd count exists, add 1 for the center.

Algorithm

Count each character in s.

Initialize:

length = 0
has_odd = False

For each character count count:

1. Add the even part:

count // 2 * 2

2. If count is odd, remember that we can place one odd character in the center.

At the end:

1. If has_odd is true, add 1.
2. Return length.

Correctness

Every palindrome has mirrored left and right halves.

Therefore, except for possibly one center character, every used character must appear in pairs.

For a character with count c, the maximum number of copies that can be used in pairs is:

(c // 2) * 2

The algorithm adds exactly this paired amount for every character.

If at least one character has an odd count, then after using its even part, one copy remains. A palindrome can use exactly one such leftover character as the center. The algorithm adds 1 in this case.

It never adds more than one odd leftover, because a palindrome can have only one center.

Thus the algorithm uses the maximum possible number of characters while still satisfying the palindrome structure, so the returned length is correct.

Complexity

Here n is the length of s.

Although the implementation uses a hash map, the alphabet size is bounded by lowercase and uppercase English letters.

Implementation

from collections import Counter

class Solution:
    def longestPalindrome(self, s: str) -> int:
        counts = Counter(s)

        length = 0
        has_odd = False

        for count in counts.values():
            length += (count // 2) * 2

            if count % 2 == 1:
                has_odd = True

        if has_odd:
            length += 1

        return length

Code Explanation

We count all characters:

counts = Counter(s)

For:

s = "abccccdd"

we get:

a -> 1
b -> 1
c -> 4
d -> 2

Then we scan the counts:

for count in counts.values():

For each count, we add its largest even part:

length += (count // 2) * 2

If the count is odd:

if count % 2 == 1:
    has_odd = True

then one character may be used as the center.

After all counts are processed, we add one center character if possible:

if has_odd:
    length += 1

Finally:

return length

Alternative Implementation

We can also count pairs while scanning the string.

Whenever a character count becomes even, we have formed one new pair, so we add 2.

from collections import defaultdict

class Solution:
    def longestPalindrome(self, s: str) -> int:
        counts = defaultdict(int)
        length = 0

        for ch in s:
            counts[ch] += 1

            if counts[ch] % 2 == 0:
                length += 2

        if length < len(s):
            length += 1

        return length

This version uses the same idea.

length < len(s) means at least one character was left unused, so we can put one leftover character in the center.

Testing

def test_longest_palindrome():
    s = Solution()

    assert s.longestPalindrome("abccccdd") == 7
    assert s.longestPalindrome("a") == 1
    assert s.longestPalindrome("bb") == 2
    assert s.longestPalindrome("Aa") == 1
    assert s.longestPalindrome("ccc") == 3
    assert s.longestPalindrome("bananas") == 5
    assert s.longestPalindrome("abc") == 1

    print("all tests passed")

Test Notes