All problems

Longest Palindrome

Easy · hash map

You are given a string s made of English letters. Using some or all of its letters, rearranged in any order you like, build the longest palindrome you can (a string that reads the same forwards and backwards). Return its length.

Each letter of s can be used at most once. Letters are case-sensitive: "a" and "A" are different letters, so "aA" is not a palindrome.

You only need the length, not the palindrome itself. Since s has at least one letter, the answer is always at least 1.

Examples

Example 1

Input: s = "racecars"

Output: 7

The letters r, a and c appear twice each, and e and s once. For example "racecar" is a palindrome of length 7, built from all three pairs and one single letter in the middle.

Example 2

Input: s = "aAaA"

Output: 4

Two a and two A can form "aAAa". Capital and small letters are counted separately.

Example 3

Input: s = "Zz"

Output: 1

Z and z are different letters, so only one of them can be used.

Constraints

• 1 <= len(s) <= 10^4
• s consists of lowercase and uppercase English letters only.