You're given a string s made of lowercase and uppercase English letters. Using some or all of those letters — each one at most as many times as it appears in s — build the longest palindrome you can, and return its length.
Letters are case-sensitive: "Aa" is not a palindrome.
You only need the length, not the palindrome itself.
Examples
Example 1
Input: s = "abacabad"
Output: 7
The letters are a×4, b×2, c×1, d×1. All four as and both bs fit around a single leftover letter in the middle, for example "abacaba".
Example 2
Input: s = "Aa"
Output: 1
'A' and 'a' are different letters, so only one of them can be used.
Example 3
Input: s = "bananas"
Output: 5
One possible answer is "anana". The b and s can't both be used — only one letter may sit unpaired in the middle.
Example 4
Input: s = "zzzzzz"
Output: 6
Every letter is used: "zzzzzz" is already a palindrome.
Example 5
Input: s = "Mississippi"
Output: 11
i×4, s×4 and p×2 all pair up, and the single M goes in the middle.
Constraints
1 <= s.length <= 2000sconsists of lowercase and/or uppercase English letters only.