CMPUT 275 - Tangible Computing
Morning Problem: Creating Palindromes
Description
As you may know, a palindrome is a phrase that reads the same forwards as it does backwards, a quick example of this is the word “race car”.
For this problem you will be given a string s of length n, your goal is to report the length
of the largest string you can create by rearranging the letters of s such that the resulting
string is a palindrome.
Input
The first line of input will contain an integer n (1 ≤ n ≤ 100, 000), the length of s.
On the following line you will be given a string s (containing only lower case letters a - z)
of length n.
Output
Output a single line containing the length of the largest possible palindrome created by rearranging the letters of s.
Sample Input 1
3
abc
Sample Output 1
1
Explanation
There are no pairs of letters that allow us to create a larger palindrome, all possible palindromes with this given input are “a”, “b” and “c”.
Sample Input 2
4
aefa
Sample Output 2
3
Explanation
Since there is a pair of the letter a, we are able to create a palindrome of length 3, one
example of such a palindrome given this input is “afa”.
Sample Input 3
6
abacbc
Sample Output 3
6
Explanation
In this example all letters found are in pairs, this allows us to create a palindrome containing
all letters of s, one such example is the string “abccba”.
