Given a string s, your task is to find this longest possible palindrome. You may use any number of the characters from s, and arrange them in any order (so long as it results in a palindrome).

If there are multiple longest palindromes that can be formed, return the one among them that's lexicographically smallest.

Example

For s = "aaabb", the output should be maximalPalindrome(s) = "ababa".

There are two possible palindromes of length 5 that can be obtained ("ababa" and "baaab"), but "ababa" is lexicographically smaller, thus it is the answer.

For s = "aaabbbcc", the output should be maximalPalindrome(s) = "abcacba".

It's not possible to form a palindrome of length 8, but from several palindromes of length 7, "abcacba" is the lexicographically smallest, thus it is the answer.

It's simpler to just create the longest possible palindrome out of a set of characters, but how can we do it efficiently making sure it's lexicographically smallest?

def maximalPalindrome(s):
    from collections import Counter
    counter = Counter(s)
    from collections import deque
    palindrome = deque()
	
	currLen = 0
	for char in counter:
		pairs = counter[char] // 2
		for _ in pairs:
			palindrome.append(counter[char])
			palindrome.appendleft(counter[char])
			currLen += 2
		# if we stll have an even length of chars in palindrome then we can
		# potentially add a 'center'
		if currLen % 2 == 0 and counter[char] % 2 == 1:
			palindrome.insert(currLen // 2, counter[char])
			currLen += 1