Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Palindrome Permutation II in Java: Build Half, Then Mirror

Understand odd frequencies, duplicate-free half permutations, shared state restoration, and a step-through recursion tree with fully commented Java.

MediumRecursion and backtrackingPattern: recursion, backtracking, hashing

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

  1. Example 1 Case 1

    Input
    s=aabb
    Output
    [abba, baab]

    Two unique left halves.

  2. Example 2 Case 2

    Input
    s=abc
    Output
    []

    Three odd frequencies are impossible.

  3. Example 3 Case 3

    Input
    s=aaaabb
    Output
    [aabbaa, abaaba, baaaab]

    Repeated half letters do not duplicate results.

Solve on LeetCode ↗

Hints Optional

Hints become more specific one step at a time.
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:

Java
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

Java
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”

Worked example · read from top to bottom
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"; return

An 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

Numbered illustrated dry run for Palindrome Permutation II; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
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.

“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 Reasoning

Compare a different recursive promise and how its parent resumes.

Back to Recursion and backtracking →