Palindrome permutation: can the letters form a palindrome

Given a string, decide whether some rearrangement of its characters reads the same forwards and backwards. Then, when one exists, build it: return the lexicographically smallest palindrome that uses exactly those characters.

Interface

Unless you agree on a different interface with the interviewer, assume:

• can_form_palindrome(s: str) -> bool
• smallest_palindrome(s: str) -> str — the lexicographically smallest palindromic rearrangement of s, or "" when none exists.

Example

can_form_palindrome("carerac")  ->  True
can_form_palindrome("code")     ->  False
smallest_palindrome("aabbc")    ->  "abcba"
smallest_palindrome("carerac")  ->  "acrerca"
smallest_palindrome("code")     ->  ""

Constraints

• 1 <= len(s) <= 200,000; lowercase English letters only.

Clarifying questions

• Which characters can appear: lowercase only, or any Unicode? Are case and spaces significant?
• Do you want any palindrome, or a specific one such as the smallest?
• Is the input possibly empty?

What a strong answer covers

• The rule: a rearrangement is a palindrome exactly when at most one character occurs an odd number of times.
• Counting with a 26-entry array (or a bitmask that flips per character, then "at most one bit set"), O(n) time and O(1) space.
• Building the smallest palindrome: lay out half of each character's count in alphabetical order, put the single odd character in the centre, mirror the first half.
• Tests: one character, all the same character, two odd counts, an even-length palindrome.

Follow-ups

• Return every distinct palindromic rearrangement (backtracking over half the counts).
• Count the substrings that can be rearranged into a palindrome, using prefix bitmasks.
• Characters may be any Unicode code point.