203. Generate Palindromic Permutations Of String
Generate Palindromic Permutations Of String
You are given a string s.
Return all distinct permutations of s that are palindromes.
A palindrome is a string that reads the same from left to right and from right to left.
If no palindromic permutation can be formed using all characters of s, return an empty list.
The output must not contain duplicate strings.
To make the output deterministic, return the palindromic permutations in lexicographical ascending order.
Class Definition
Implement the class PalindromicPermutations.
Constructor
PalindromicPermutations()
Initializes the object.
Method Signature
List<String> generatePalindromes(String s)
- Returns all distinct palindromic permutations of
s.
- Each returned string must use every character from
s exactly once.
- If no palindromic permutation is possible, return an empty list.
- The returned list must be sorted in lexicographical order.
Constraints
1 ≤ s.length() ≤ 16s contains only lowercase English letters.- The output list must not contain duplicate strings.
- The output list must be in lexicographical order.
- No parameter value will be
null.
Examples
Example 1
Input:
PalindromicPermutations solver = new PalindromicPermutations()
solver.generatePalindromes(s = "aabb")
Output:
["abba", "baab"]
Explanation:
The string can be rearranged into two distinct palindromes: "abba" and "baab". They are returned in lexicographical order.
Example 2
Input:
PalindromicPermutations solver = new PalindromicPermutations()
solver.generatePalindromes(s = "aabbcc")
Output:
["abccba", "acbbca", "baccab", "bcaacb", "cabbac", "cbaabc"]
Explanation:
All characters have even frequency, so palindromic permutations are possible. The returned list contains every distinct palindrome in lexicographical order.
Example 3
Input:
PalindromicPermutations solver = new PalindromicPermutations()
solver.generatePalindromes(s = "abc")
Output:
[]
Explanation:
More than one character has an odd frequency, so no palindromic permutation can be formed.
Example 4
Input:
PalindromicPermutations solver = new PalindromicPermutations()
solver.generatePalindromes(s = "aaa")
Output:
["aaa"]
Explanation:
The only distinct permutation of the string is already a palindrome.