Problem statement
Rearrange every character of a string into all unique palindromes. A palindrome reads identically from either end. If none is possible, return an empty list; output order does not matter.
The original takeUforward prompt uses 1–16 lowercase English letters. “aabb” gives [“abba”,“baab”]; “abc” gives [].
This is not palindrome partitioning. We rearrange all characters; we do not cut the original string into palindromic substrings.
Constraints & requirements
- CONTRACT
- Preserve the character frequencies and return no duplicate palindrome.
Examples 3 test cases
Example 1 Case 1
- Input
s=aabb- Output
[abba, baab]
Two unique left halves.
Example 2 Case 2
- Input
s=abc- Output
[]
Three odd frequencies are impossible.
Example 3 Case 3
- Input
s=aaaabb- Output
[aabbaa, abaaba, baaaab]
Repeated half letters do not duplicate results.
Hints Optional
01Find the smaller problem
Letters outside the center need mirrored partners.
02Define the state
More than one odd frequency is impossible; permute the half frequencies, then mirror.
03Connect the recurrence
Branch by letter type, decrement its half count, recurse, and restore both the count and path.
How to think before coding
Count characters before searching. A palindrome requires matching outer pairs, so more than one odd frequency makes the answer impossible. Reserve the optional odd center and permute only half of each frequency. Every completed half determines the full palindrome. Avoid duplicate half choices and undo reservations; do not confuse rearrangement with partitioning the original order.
Brute force and its wasted work
Your local practice/PalindromePermutation.java checks whether a palindrome is possible, then swaps characters to generate unique full permutations and tests each leaf. Its per-level set has a different job from the path: remember which letters were already tried at this position, so do not remove letters from that set when undoing a swap. The half-building solution below preserves that uniqueness principle while avoiding non-palindromic full permutations.
Generate all n! position permutations, check each for symmetry in O(n), and use a Set to remove duplicates. That is O(n·n!) upper-bound time, plus recursion and stored results. Many permutations are not palindromes; repeated characters also create duplicate routes.
A small-string checker illustrates the test:
static boolean isPalindrome(String text) {
for (int left = 0, right = text.length() - 1; left < right; left++, right--) {
if (text.charAt(left) != text.charAt(right)) return false; // One unequal mirror pair rejects it.
}
return true; // Every compared pair matched, including a possible unpaired center.
}The improved approach never generates the invalid full permutations. It permutes only the required left-half inventory.
Intuition: pairs on the outside, one center
Every non-center position has a mirrored partner with the same letter. Therefore all frequencies must be even, except at most one odd-frequency letter, which can occupy the center.
For “aabbc”: left-half inventory is one a and one b; center is c. Choosing left=“ab” forces right=“ba”, producing “abcba”. Choosing left=“ba” produces “bacab”.
Why “at most one odd,” not “exactly one”? Even-length palindromes have no center. For an odd length, parity guarantees exactly one odd frequency when a palindrome is possible.
Duplicate-free recursive solution
public static List<String> palindromes(String s) {
int[] halfCounts = new int[26]; // At first these are full lowercase-letter frequencies.
for (char c : s.toCharArray()) halfCounts[c - 'a']++; // Count repeated letters by identity.
String middle = ""; // Even lengths have no center character.
int odd = 0; // More than one unpaired letter makes a palindrome impossible.
for (int letter = 0; letter < 26; letter++) { // Examine all allowed character types.
if (halfCounts[letter] % 2 == 1) { // This letter needs the unique center position.
odd++; // Track how many different letters need that position.
middle = String.valueOf((char) ('a' + letter)); // Save the candidate center.
}
halfCounts[letter] /= 2; // Each mirrored pair contributes one letter to the left half.
}
List<String> answer = new ArrayList<>(); // No output is a valid impossible-case result.
if (odd > 1) return answer; // Two odd letters cannot both occupy the single center.
permuteHalf(halfCounts, s.length() / 2, new StringBuilder(), middle, answer); // Generate only half.
return answer; // Each unique half determines exactly one unique palindrome.
}
private static void permuteHalf(int[] counts, int length, StringBuilder left,
String middle, List<String> answer) {
if (left.length() == length) { // Every required left-half character has been placed.
String right = new StringBuilder(left).reverse().toString(); // Mirror a copy, not shared left.
answer.add(left.toString() + middle + right); // Assemble the full symmetric string.
return; // No remaining position needs another choice.
}
for (int letter = 0; letter < 26; letter++) { // Branch by letter type, not identical occurrences.
if (counts[letter] == 0) continue; // No copy of this letter remains for this position.
counts[letter]--; // Reserve one copy for the current recursive branch.
left.append((char) ('a' + letter)); // Extend this shared path by one character.
permuteHalf(counts, length, left, middle, answer); // Solve the shorter remaining task.
left.deleteCharAt(left.length() - 1); // Restore the path for the next letter choice.
counts[letter]++; // Restore availability; siblings must start from the same inventory.
}
}Why branch by letter type? Two copies of a are indistinguishable. At a position, “choose a” is one branch, not one branch for each physical occurrence. Decrementing a frequency tracks how many remain without duplicating answers.
Why restore both left and counts? The builder records the chosen order; counts records remaining inventory. Both are shared objects. Undoing only one leaves a sibling with a different starting state.
Why mirror a copy? Reversing the shared left builder would corrupt the prefix that waiting frames expect.
Recursion tree: “aabb”
left="" ; remaining a:1 b:1
├─ choose a → left="a" ; a:0 b:1
│ └─ choose b → left="ab" ; a:0 b:0
│ mirror → "abba"; return
└─ choose b → left="b" ; a:1 b:0
└─ choose a → left="ba" ; a:0 b:0
mirror → "baab"; returnAn unavailable letter causes no recursive call. For “aaaabb”, the half inventory a:2, b:1 generates only aab, aba, baa; output is aabbaa, abaaba, baaaab.
Dry run: restoration is the important part

Read the text transcript
| Event | left | Remaining half inventory |
|---|---|---|
| Start | “” | a:1, b:1 |
| Choose a | “a” | a:0, b:1 |
| Choose b | “ab” | a:0, b:0 |
| Save “abba” | “ab” | unchanged |
| Return, undo b | “a” | a:0, b:1 |
| Return, undo a | “” | a:1, b:1 |
| Choose b | “b” | a:1, b:0 |
The second root branch must start with the same inventory as the first. In the dry run, restore the frequency and remove the last half-character before following the next loop iteration.
Why this is correct
A valid palindrome has at most one odd frequency. Dividing counts by two gives exactly the left-half inventory; the odd letter is forced into the center. Every unique permutation of that inventory is explored once. Mirroring it yields a valid palindrome using all original characters. Conversely, every valid palindrome has one such left half, so none is missed.
Complexity
Let m=floor(n/2), and let P=m! divided by the factorials of the half-letter counts be the number of unique outputs. Copying each full palindrome costs O(n).
The recursion visits valid partial permutations and tries 26 letter types per non-leaf. For this fixed alphabet, total time is O(n + n·P) (equivalently O(n + 26mP)); auxiliary counts/path/call-stack space is O(n+26), excluding O(n·P) output storage. The impossible case stops after the O(n+26) frequency scan.
This is output-sensitive; an algorithm cannot return P length-n strings in O(n) total time.
Mistakes, edge cases, and doubts
- More than one odd count means impossible, not “put both in the center.”
- A Set can hide duplicate generation but does not remove the wasted recursive work.
- “a” → [“a”]; “aaaa” → [“aaaa”]; “abc” → []; “aabbc” → two outputs.
- Verify each output is a palindrome, has the original frequency table, and appears once.
- This code assumes lowercase English letters. Arbitrary Unicode needs a different character representation and frequency map.
Recognition and related practice
“Rearrange + palindrome + duplicates” suggests frequencies, a forced center, and unique half permutations. Compare binary strings with a local restriction: both generate only valid prefixes, but this problem consumes an inventory.
Company research note
No exact, sufficiently attributable public candidate report was verified on 3 October 2026. Aggregated company lists and the different “Palindrome Permutation” boolean problem are not enough to assign a company badge here.
Final takeaway
Validate parity once. Build one unique half. The rest of the palindrome is forced.
Download all tested Java solutions. These methods use Java 17+; import java.util.* in a standalone program. Use the Java comments and static dry run together to follow each call, return and update.
Practice next
Next lessonPrint an Immutable Linked List in Reverse: Java Call-Stack ReasoningCompare a different recursive promise and how its parent resumes.