Rearrange the characters of a string to form the lexicographically smallest palindrome, if one can be formed.
Smallest Palindromic Rearrangement II
gfgProblem
Given a string s, rearrange all of its characters to form a palindrome that is lexicographically smallest among all possible palindromic rearrangements.
If no palindrome can be formed using all characters of s, return an empty string.
A string is lexicographically smaller than another string if at the first position where they differ, the character in the first string comes earlier in alphabetical order.
Notes
- You must use every character exactly once.
- The resulting string must read the same forward and backward.
- If multiple palindromic rearrangements exist, choose the smallest one in lexicographic order.
Input Format
- A single string
sconsisting of lowercase English letters.
Output Format
- Return the lexicographically smallest palindrome that can be formed using all characters of
s. - If impossible, return
"".
Constraints
scontains only lowercase English letters.
Example 1
Input
s = "aabb"
Output
"abba"
Explanation
Two palindromes are possible: abba and baab. The lexicographically smaller one is abba.
Example 2
Input
s = "bbaa"
Output
"abba"
Explanation
The character counts are the same as in the first example, so the smallest palindromic rearrangement is still abba.
Show 1 more example
Example 3
Input
s = "abc"
Output
""
Explanation
Each character appears once, so more than one character has an odd frequency. No palindrome can be formed.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.