Smallest palindrome from a symmetric string's letters

You are given a string s of lowercase English letters that is already a palindrome. Rearrange all of its characters to form a new palindrome, and return the one that comes first in dictionary (lexicographic) order.

Implement:

def smallest_palindrome(s: str) -> str: ...

If the input turns out not to allow any palindrome, return the empty string.

Constraints

• 1 <= len(s) <= 10^5
• s contains only 'a' to 'z'.

Example 1

Input:  s = "cbabc"
Output: "bcacb"

The letters are two b, two c and one a. The a must sit in the middle, and putting b before c on the left gives the smallest result.

Example 2

Input:  s = "daccad"
Output: "acddca"

Every letter appears an even number of times, so there is no middle character.