# 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:

```python
"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

| Item | Meaning |
|---|---|
| Input | A string `s` |
| Output | Length of the longest palindrome that can be built |
| Rearrangement | Allowed |
| Case sensitivity | `"A"` and `"a"` are different letters |
| Return type | Integer |

Example function shape:

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

## Examples

Example 1:

```python
s = "abccccdd"
```

The answer is:

```python
7
```

One possible palindrome is:

```python
"dccaccd"
```

Its length is `7`.

Character counts:

| Character | Count |
|---|---:|
| `a` | 1 |
| `b` | 1 |
| `c` | 4 |
| `d` | 2 |

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:

```python
4 + 2 + 1 = 7
```

Example 2:

```python
s = "a"
```

The answer is:

```python
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:

```python
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:

```python
"racecar"
```

The character `e` appears once in the center.

```python
"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:

```python
length = 0
has_odd = False
```

For each character count `count`:

1. Add the even part:

```python
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:

```python
(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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We count each character once |
| Space | `O(1)` | There are at most 52 English letters |

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

```python
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:

```python
counts = Counter(s)
```

For:

```python
s = "abccccdd"
```

we get:

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

Then we scan the counts:

```python
for count in counts.values():
```

For each count, we add its largest even part:

```python
length += (count // 2) * 2
```

If the count is odd:

```python
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:

```python
if has_odd:
    length += 1
```

Finally:

```python
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`.

```python
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

```python
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

| Test | Why |
|---|---|
| `"abccccdd"` | Standard example with several pairs and one center |
| `"a"` | Single character |
| `"bb"` | Entire string can be used |
| `"Aa"` | Case sensitivity matters |
| `"ccc"` | Odd count can use all characters |
| `"bananas"` | Multiple odd and even counts |
| `"abc"` | Only one character can be used |