A mosaic artisan has a bag of leftover tiles from previous jobs. Each tile is stamped with a single-letter code (uppercase and lowercase letters denote different tile finishes, so they are never interchangeable), given as a string s where each character is one tile.
The artisan wants to lay some of these tiles out in a single row to form the longest possible palindromic frieze — a border that reads identically from left to right and from right to left. Tiles may be freely reordered, and not every tile needs to be used. Determine the maximum number of tiles that can appear in such a frieze.
A single line containing the string s of tile codes.
Print a single integer: the length of the longest palindrome that can be built using tiles from s.
Example 1
Input
banana
Expected
5
Explanation
The tile counts are a:3, n:2, b:1. Taking floor(count/2) pairs from each letter gives 1 pair of 'a' (2 tiles, with 1 'a' left over), 1 pair of 'n' (2 tiles, none left over), and 0 pairs of 'b' (1 tile left over). The paired tiles contribute 2 + 2 + 0 = 4 tiles to the frieze, and since at least one letter (a or b) has a leftover tile, one more tile can sit in the center, giving 4 + 1 = 5. A valid frieze of that length is "anana", built from three 'a' tiles and two 'n' tiles.
Example 2
Input
A
Expected
1
Explanation
There is only one tile, so the longest possible palindrome is that single tile by itself, giving length 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →