Loading problem...
Given a string consisting of lowercase English characters, your task is to generate all possible unique rearrangements of its characters that form valid palindromes. A palindrome is a string that reads the same forwards and backwards.
If the given string cannot be rearranged to form any palindrome (i.e., no permutation of its characters results in a palindrome), return an empty list.
The resulting palindromes should be returned without duplicates, and the order of the output does not matter.
Key Insight: A string can form a palindrome if and only if at most one character has an odd frequency count. When characters are rearranged symmetrically around an optional center character (the one with odd frequency, if any), palindromic sequences emerge.
s = "aabb"["abba","baab"]The string "aabb" has two 'a's and two 'b's. Both characters appear an even number of times, making palindrome formation possible. The valid rearrangements are "abba" (placing 'b' at the center with 'a' on both ends) and "baab" (placing 'a' at the center with 'b' on both ends). Both strings read the same forwards and backwards.
s = "abc"[]The string "abc" has three distinct characters, each appearing exactly once (odd frequency). For a palindrome, at most one character can have an odd frequency. Since all three have odd counts, no palindrome can be formed, resulting in an empty output.
s = "aab"["aba"]The string "aab" has two 'a's and one 'b'. Only 'b' has an odd frequency, which is permissible. The character 'b' must be placed at the center, with the 'a' characters mirrored on either side, yielding the single palindrome "aba".
Constraints