Problem Description

Given a string s, you need to find all possible palindromic permutations of the string without duplicates. A palindromic permutation is a rearrangement of the characters that forms a palindrome (reads the same forwards and backwards).

The task requires you to:

1. Check if the given string can form any palindrome permutation
2. If yes, generate all unique palindromic permutations
3. If no palindromic permutation is possible, return an empty list

For a string to form a palindrome:

• If the length is even, every character must appear an even number of times
• If the length is odd, exactly one character can appear an odd number of times (this character would be in the middle)

For example:

• Input: "aab" → Output: ["aba"] (only one palindromic permutation possible)
• Input: "abc" → Output: [] (no palindromic permutation possible since all three characters appear once)
• Input: "aabb" → Output: ["abba", "baab"] (multiple palindromic permutations possible)

The solution uses a depth-first search approach to build palindromes by:

1. First counting character frequencies to check if a palindrome is possible
2. Identifying any character that appears an odd number of times (which would be the middle character)
3. Recursively building the palindrome from the center outward by adding matching characters on both sides

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem involves string manipulation and permutation generation, not graph traversal with nodes and edges.

Need to solve for kth smallest/largest?

• No: We need to find all palindromic permutations, not a specific kth element.

Involves Linked Lists?

• No: The problem works with strings and character frequencies, not linked list data structures.

Does the problem have small constraints?

• Yes: Generating all permutations has factorial time complexity, which is only feasible for small inputs. The problem expects us to generate all possible palindromic arrangements, which naturally limits the input size.

Brute force / Backtracking?

• Yes: We need to explore all possible ways to arrange characters to form palindromes. Backtracking is perfect here because:
  • We build solutions incrementally (adding characters symmetrically from center outward)
  • We need to explore multiple branches (trying different characters at each position)
  • We can prune invalid paths early (when character counts don't allow palindrome formation)
  • We need to generate all valid solutions, not just one

Conclusion: The flowchart correctly leads us to use a Backtracking approach. The solution builds palindromes from the center outward by recursively placing matching character pairs on both sides, backtracking when necessary to explore all valid combinations.

Intuition

To generate palindromic permutations, we need to understand what makes a palindrome possible. A palindrome reads the same forwards and backwards, meaning characters must appear in mirror positions. This gives us a key insight: most characters must appear in pairs (one for each side of the palindrome).

The first observation is about character frequency constraints:

• For even-length palindromes: every character must appear an even number of times
• For odd-length palindromes: exactly one character can appear an odd number of times (this goes in the middle)

If we have more than one character with odd frequency, it's impossible to form any palindrome, so we return an empty list immediately.

The second insight is about construction strategy. Instead of generating all permutations and checking which ones are palindromes (which would be inefficient), we can build palindromes directly. Since palindromes are symmetric, we only need to build half of the string - the other half is determined automatically.

The clever approach is to build from the center outward. We start with the middle character (if there is one with odd frequency), then recursively add matching pairs of characters on both sides. This ensures every string we generate is guaranteed to be a palindrome.

For backtracking, we:

1. Pick a character that has at least 2 occurrences remaining
2. Place one on the left and one on the right of our current palindrome
3. Decrease the count by 2
4. Recursively continue building
5. When we backtrack, restore the count by adding 2 back

This way, we explore all possible ways to arrange the character pairs while maintaining the palindrome property throughout the construction process. The depth-first search naturally handles generating all unique palindromic permutations without duplicates.

Solution Approach

The implementation uses a depth-first search (DFS) with backtracking to generate all palindromic permutations. Here's how the solution works:

Step 1: Count Character Frequencies

cnt = Counter(s)

We use Python's Counter to count the frequency of each character in the input string. This helps us quickly check if a palindrome is possible and track available characters during construction.

Step 2: Check Palindrome Feasibility and Find Middle Character

mid = ''
for c, v in cnt.items():
    if v & 1:  # Check if frequency is odd using bitwise AND
        if mid:
            return []  # More than one odd frequency - impossible
        mid = c
        cnt[c] -= 1

We iterate through the character counts to:

• Identify characters with odd frequencies using v & 1 (bitwise check for odd numbers)
• If we find more than one character with odd frequency, return empty list (no palindrome possible)
• Store the odd-frequency character as mid (it will be the center of our palindrome)
• Decrease its count by 1 since we've "used" it for the middle position

Step 3: DFS Backtracking Function

def dfs(t):
    if len(t) == len(s):
        ans.append(t)
        return
    for c, v in cnt.items():
        if v > 1:
            cnt[c] -= 2
            dfs(c + t + c)
            cnt[c] += 2

The recursive function builds palindromes by:

• Base case: When the constructed string t reaches the original length, we've found a complete palindrome
• Recursive case: For each character with at least 2 remaining occurrences:
  • Subtract 2 from its count (using one for each side)
  • Add the character to both ends: c + t + c creates a new palindrome with c on both sides
  • Recursively continue building with the updated string
  • Backtrack by restoring the count (cnt[c] += 2)

Step 4: Initialize and Execute

ans = []
dfs(mid)
return ans

We start the DFS with the middle character (empty string if even-length palindrome) and collect all generated palindromes in the ans list.

The algorithm efficiently generates only valid palindromes by:

• Building from center outward ensures symmetry
• Using character counts prevents invalid combinations
• Backtracking explores all possible arrangements
• The approach avoids generating duplicates since we work with character frequencies rather than individual character positions

Time complexity: O(n! / (2^(n/2))) where n is the length of the string, as we generate all valid palindromic permutations. Space complexity: O(n) for the recursion stack and character count storage.

Example Walkthrough

Let's walk through the solution with the input string s = "aabb".

Step 1: Count Character Frequencies

• Count: {'a': 2, 'b': 2}
• All characters have even frequencies

Step 2: Check Palindrome Feasibility

• Iterate through counts:
  • 'a': frequency 2 (even) - skip
  • 'b': frequency 2 (even) - skip
• No character has odd frequency, so mid = '' (empty string)
• The string can form palindromes!

Step 3: DFS Backtracking Process

Starting with dfs(''):

First Branch - Choose 'a':

• Current string: '', Counts: {'a': 2, 'b': 2}

• Pick 'a' (has count ≥ 2)

• Reduce count: {'a': 0, 'b': 2}

• New string: 'a' + '' + 'a' = 'aa'

• Call dfs('aa')

  Nested call with 'aa':

  • Current string: 'aa', Counts: {'a': 0, 'b': 2}
  • Only 'b' has count ≥ 2
  • Pick 'b': {'a': 0, 'b': 0}
  • New string: 'b' + 'aa' + 'b' = 'baab'
  • Call dfs('baab')

  Base case reached:

  • String length 4 = original length 4
  • Add 'baab' to answer
  • Return and backtrack: restore 'b' count to 2

• Backtrack from 'aa': restore 'a' count to 2

Second Branch - Choose 'b':

• Current string: '', Counts: {'a': 2, 'b': 2}

• Pick 'b' (has count ≥ 2)

• Reduce count: {'a': 2, 'b': 0}

• New string: 'b' + '' + 'b' = 'bb'

• Call dfs('bb')

  Nested call with 'bb':

  • Current string: 'bb', Counts: {'a': 2, 'b': 0}
  • Only 'a' has count ≥ 2
  • Pick 'a': {'a': 0, 'b': 0}
  • New string: 'a' + 'bb' + 'a' = 'abba'
  • Call dfs('abba')

  Base case reached:

  • String length 4 = original length 4
  • Add 'abba' to answer
  • Return and backtrack

Final Result: ['baab', 'abba']

The algorithm builds palindromes from the center outward by:

1. Starting with an empty center (since all frequencies are even)
2. Adding matching pairs of characters on both sides
3. Exploring all possible orderings through backtracking
4. Guaranteeing each generated string is a palindrome by construction

Solution Implementation

Time and Space Complexity

Time Complexity: O(n! * n) where n is the length of the input string.

The algorithm generates all possible palindromic permutations using backtracking. In the worst case where all characters appear an even number of times (or at most one character appears odd times), we need to place n/2 pairs of characters. The number of ways to arrange these pairs is at most (n/2)!. For each complete permutation generated, we spend O(n) time to construct the string by concatenating characters. Therefore, the overall time complexity is O((n/2)! * n), which simplifies to O(n! * n).

Space Complexity: O(n) for the recursion stack and auxiliary data structures.

The space complexity consists of:

• O(n) for the cnt Counter to store character frequencies
• O(n) for the recursion stack depth, which goes up to n/2 levels in the worst case
• O(n) for each string being constructed during recursion
• O(k * n) for storing the final answer list, where k is the number of valid palindromic permutations

Excluding the output space, the space complexity is O(n). If we include the output space, it becomes O(k * n) where k can be at most (n/2)! valid palindromes.

Common Pitfalls

1. Forgetting to Handle the Middle Character Correctly

Pitfall: A common mistake is not properly handling the middle character for odd-length palindromes. Developers often forget to:

• Decrement the count of the odd-frequency character after identifying it as the middle
• Initialize the DFS with this middle character

Why it happens: When a character has odd frequency (e.g., 'a' appears 3 times), one instance must be placed in the middle, and the remaining even count (2) should be used for symmetric placement.

Incorrect approach:

# Wrong: Not decrementing the odd character count
for char, count in char_frequency.items():
    if count % 2 == 1:
        middle_char = char
        # Missing: char_frequency[char] -= 1

Correct approach:

for char, count in char_frequency.items():
    if count % 2 == 1:
        middle_char = char
        char_frequency[char] -= 1  # Critical: reduce count by 1

2. Using >= Instead of > in the DFS Condition

Pitfall: Using if count >= 2 seems logical, but using if count > 1 is clearer and equivalent. Some developers might mistakenly use if count > 0 or if count >= 1.

Why it happens: Confusion about needing pairs of characters for palindrome construction.

Incorrect approach:

# Wrong: This would try to use single characters
if count >= 1:  # or if count > 0:
    char_frequency[char] -= 2  # This would fail when count is 1

Correct approach:

if count >= 2:  # or equivalently: if count > 1
    char_frequency[char] -= 2

3. Not Properly Implementing Backtracking

Pitfall: Forgetting to restore the character count after the recursive call, which leads to incorrect results for subsequent iterations.

Why it happens: In backtracking algorithms, every state change before recursion must be reversed after recursion.

Incorrect approach:

def build_palindrome(current_middle):
    for char, count in char_frequency.items():
        if count >= 2:
            char_frequency[char] -= 2
            build_palindrome(char + current_middle + char)
            # Missing: char_frequency[char] += 2

Correct approach:

def build_palindrome(current_middle):
    for char, count in char_frequency.items():
        if count >= 2:
            char_frequency[char] -= 2
            build_palindrome(char + current_middle + char)
            char_frequency[char] += 2  # Critical: restore the count

4. Incorrect Palindrome Validation Logic

Pitfall: Incorrectly checking if a palindrome can be formed by counting odd frequencies wrong or allowing multiple odd-frequency characters.

Why it happens: Misunderstanding the palindrome formation rule - at most one character can have odd frequency.

Incorrect approaches:

# Wrong: Checking for exactly one odd (fails for even-length palindromes)
if odd_count != 1:
    return []

# Wrong: Not checking at all
# Just proceed without validation

Correct approach:

odd_count = 0
for char, count in char_frequency.items():
    if count % 2 == 1:
        odd_count += 1
        if odd_count > 1:  # More than one odd frequency
            return []
        middle_char = char
        char_frequency[char] -= 1

5. Building Palindromes in the Wrong Direction

Pitfall: Trying to build palindromes from left to right instead of from center outward, which complicates the logic and can lead to duplicates.

Why it happens: Natural inclination to build strings from left to right.

Incorrect approach:

# Wrong: Building from one end
def build_palindrome(left_half, right_half):
    # Complex logic to ensure symmetry
    # Prone to generating duplicates

Correct approach:

# Building from center outward guarantees symmetry
build_palindrome(char + current_middle + char)

Prevention Tips:

1. Always validate palindrome possibility before attempting to generate permutations
2. Carefully track character counts and remember to restore them during backtracking
3. Test with edge cases: empty string, single character, all same characters, no possible palindrome
4. Draw out the recursion tree for small examples to verify the logic
5. Use clear variable names (e.g., middle_char instead of just mid) to avoid confusion