> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/string/409.-longest-palindrome.md).

# 409. Longest Palindrome

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example `"Aa"` is not considered a palindrome here.

**Note:**\
Assume the length of given string will not exceed 1,010.

**Example:**

```
Input:
"abccccdd"

Output:
7

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

```cpp
int longestPalindrome(string s) { // time: O(n); space: O(1)
    vector<int> record(52, 0);
    int odd = 0;
    for (char ch : s) {
        if (isupper(ch)) ++record[ch - 'A'];
        else ++record[ch - 'a' + 26];
    }
    for (int cnt : record) {
        if (cnt & 1) ++odd;
    }
    return s.length() - odd + (odd > 0);
}
```

```cpp
int longestPalindrome(string s) { // time: O(n); space: O(n)
    int pair = 0;
    unordered_set<char> st;
    for (char ch : s) {
        if (st.count(ch)) {
            st.erase(ch);
            ++pair;
        } else {
            st.insert(ch);
        }
    }
    return 2 * pair + !st.empty();
}
```