LeetCode 267 - Palindrome Permutation II

LeetCode Problem 267

Difficulty: 🟡 Medium
Topics: Hash Table, String, Backtracking

Solution

Problem Understanding

The problem asks us to generate every unique palindrome that can be formed by rearranging the characters of a given string.

A palindrome is a string that reads the same forward and backward. For example, "abba" and "racecar" are palindromes. The task is not to determine whether the original string is already a palindrome. Instead, we must consider all possible permutations of the characters and return every distinct arrangement that forms a palindrome.

The input is a single string s consisting only of lowercase English letters. The output should be a list of all unique palindromic permutations. If no palindrome can be formed, we return an empty list.

The constraints are important:

• The string length is at most 16
• Characters are limited to lowercase English letters

A length of 16 is small enough that backtracking is feasible, but large enough that brute force permutation generation becomes extremely expensive. Since permutations grow factorially, generating all permutations directly would quickly become impractical.

The most important observation is the condition required for a palindrome to exist:

• For even length strings, every character count must be even
• For odd length strings, exactly one character may have an odd count

This property comes from the symmetry of palindromes. Every character on the left side must have a matching character on the right side, except possibly one middle character.

Several edge cases are especially important:

• Strings with more than one odd frequency, such as "abc", cannot form any palindrome
• Strings with a single character should return that character itself
• Strings with repeated characters can create duplicate permutations if not handled carefully
• Strings like "aaaa" should produce only one palindrome, not multiple identical results

Approaches

Brute Force Approach

The brute force solution generates every possible permutation of the string, then checks whether each permutation is a palindrome.

For a string of length n, there are n! possible permutations. For each permutation, we can check whether it is a palindrome in O(n) time by comparing characters from both ends toward the center.

This approach is correct because it exhaustively examines every possible arrangement. If a palindromic permutation exists, brute force will eventually find it.

However, the approach is far too slow. Even for the maximum length of 16, the number of permutations becomes astronomically large.

Additionally, duplicate characters create repeated permutations, so we would also need a set to avoid duplicate outputs.

Optimal Approach

The key insight is that a palindrome is completely determined by its first half.

For example:

• "abba" is determined by "ab"
• "racecar" is determined by "rac" plus middle character "e"

Instead of permuting the entire string, we only need to generate unique permutations of half the characters.

The algorithm works as follows:

1. Count character frequencies
2. Verify that a palindrome is possible
3. Build a half-string using count // 2 copies of each character
4. Generate all unique permutations of this half
5. Mirror the half around the optional middle character

This dramatically reduces the search space.

For example:

• "aabb" becomes half-string "ab"
• Permutations are "ab" and "ba"
• Resulting palindromes are "abba" and "baab"

By generating only unique half permutations, we avoid duplicate full palindromes automatically.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! × n)	O(n!)	Generates every permutation and checks each one
Optimal	O((n/2)! × n)	O((n/2)!)	Generates unique permutations of only half the string

Algorithm Walkthrough

1. Count the frequency of every character using a hash map.

We need frequency information because palindrome feasibility depends entirely on character counts. A hash map allows constant-time updates and lookups. 2. Count how many characters have odd frequencies.

A palindrome can contain at most one character with an odd count. If more than one odd count exists, return an empty list immediately. 3. Identify the middle character.

If one character has an odd frequency, it must appear in the center of the palindrome. Store this character separately. 4. Build the half-string.

For each character with frequency count, add count // 2 copies to a list. This represents the left half of the palindrome.

Example:

• "aabbcc" becomes "abc"
• "aaaabb" becomes "aab"

5. Sort the half-string.

Sorting allows us to skip duplicate permutations during backtracking. 6. Use backtracking to generate all unique permutations of the half-string.

During recursion:

• Track which characters are already used
• Skip duplicates by checking adjacent equal characters
• Build permutations incrementally

7. Construct full palindromes.

For each generated half:

• Reverse the half
• Insert the middle character if one exists
• Concatenate everything together

Example:

• Half: "ab"
• Middle: ""
• Reverse: "ba"
• Result: "abba"

8. Return the list of generated palindromes.

Why it works

The algorithm works because every palindrome is symmetric. Once the left half is chosen, the right half is uniquely determined by mirroring it. The only remaining freedom is the optional middle character, which must be the unique odd-frequency character if one exists.

By generating every unique permutation of the half-string exactly once, we generate every valid palindrome exactly once.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def generatePalindromes(self, s: str) -> List[str]:
        frequency = Counter(s)

        odd_chars = [char for char, count in frequency.items() if count % 2 == 1]

        if len(odd_chars) > 1:
            return []

        middle = odd_chars[0] if odd_chars else ""

        half_chars = []

        for char, count in frequency.items():
            half_chars.extend(char * (count // 2))

        half_chars.sort()

        results = []
        used = [False] * len(half_chars)

        def backtrack(path: List[str]) -> None:
            if len(path) == len(half_chars):
                half = "".join(path)
                palindrome = half + middle + half[::-1]
                results.append(palindrome)
                return

            for i in range(len(half_chars)):
                if used[i]:
                    continue

                if i > 0 and half_chars[i] == half_chars[i - 1] and not used[i - 1]:
                    continue

                used[i] = True
                path.append(half_chars[i])

                backtrack(path)

                path.pop()
                used[i] = False

        backtrack([])

        return results

The implementation begins by counting character frequencies with Counter. This immediately gives us the information needed to determine whether a palindrome is possible.

The list comprehension collecting odd_chars identifies all characters with odd frequencies. If more than one exists, the function returns an empty list immediately because no palindrome can be formed.

The variable middle stores the single odd-frequency character if one exists. This character will occupy the center position in every generated palindrome.

The half_chars list is constructed by taking half the occurrences of every character. Since the palindrome's right half is determined automatically by mirroring, we only need to generate permutations of this half.

Sorting half_chars is crucial for duplicate avoidance. During backtracking, duplicate characters that have not yet been used in the current recursive layer are skipped.

The used array tracks which characters are already included in the current permutation path.

When a full half permutation is completed, the code constructs the palindrome by concatenating:

• The half
• The middle character
• The reversed half

Each generated palindrome is appended to results.

Go Solution

package main

import (
	"sort"
)

func generatePalindromes(s string) []string {
	frequency := make(map[rune]int)

	for _, ch := range s {
		frequency[ch]++
	}

	oddCount := 0
	middle := ""

	for ch, count := range frequency {
		if count%2 == 1 {
			oddCount++
			middle = string(ch)
		}
	}

	if oddCount > 1 {
		return []string{}
	}

	halfChars := []rune{}

	for ch, count := range frequency {
		for i := 0; i < count/2; i++ {
			halfChars = append(halfChars, ch)
		}
	}

	sort.Slice(halfChars, func(i, j int) bool {
		return halfChars[i] < halfChars[j]
	})

	results := []string{}
	used := make([]bool, len(halfChars))

	var backtrack func(path []rune)

	backtrack = func(path []rune) {
		if len(path) == len(halfChars) {
			half := string(path)

			reversed := []rune(half)
			for i, j := 0, len(reversed)-1; i < j; i, j = i+1, j-1 {
				reversed[i], reversed[j] = reversed[j], reversed[i]
			}

			palindrome := half + middle + string(reversed)
			results = append(results, palindrome)
			return
		}

		for i := 0; i < len(halfChars); i++ {
			if used[i] {
				continue
			}

			if i > 0 && halfChars[i] == halfChars[i-1] && !used[i-1] {
				continue
			}

			used[i] = true
			path = append(path, halfChars[i])

			backtrack(path)

			path = path[:len(path)-1]
			used[i] = false
		}
	}

	backtrack([]rune{})

	return results
}

The Go implementation follows the same overall strategy as the Python version. One difference is the explicit use of rune slices instead of strings during backtracking. Since Go strings are immutable, working with rune slices is more efficient for incremental construction.

Another difference is manual reversal of the half-string because Go does not provide Python-style slicing syntax like [::-1].

The function returns an empty slice when no palindrome is possible, which matches LeetCode expectations.

Worked Examples

Example 1

Input:

s = "aabb"

Step 1: Count Frequencies

Character	Count
a	2
b	2

No odd counts exist.

Middle character:

""

Step 2: Build Half String

Character	count // 2	Added
a	1	a
b	1	b

Half string:

["a", "b"]

Step 3: Generate Permutations

Half Permutation	Full Palindrome
ab	abba
ba	baab

Final result:

["abba", "baab"]

Example 2

Input:

s = "abc"

Step 1: Count Frequencies

Character	Count
a	1
b	1
c	1

Odd counts:

3

Since more than one odd count exists, no palindrome is possible.

Result:

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n/2)! × n)	Generates all unique half permutations and builds full palindromes
Space	O((n/2)!)	Stores recursion state and generated results

The dominant cost comes from generating permutations of the half-string. If the original string length is n, the half length is at most n/2. For each generated permutation, constructing the full palindrome requires O(n) time.

The recursion stack depth is at most n/2, and the output itself may contain factorially many palindromes.

Test Cases

from collections import Counter

solution = Solution()

# Provided examples
assert sorted(solution.generatePalindromes("aabb")) == ["abba", "baab"]  # basic even-length case
assert solution.generatePalindromes("abc") == []  # impossible palindrome

# Single character
assert solution.generatePalindromes("a") == ["a"]  # smallest valid input

# All identical characters
assert solution.generatePalindromes("aaaa") == ["aaaa"]  # only one unique palindrome

# Odd-length palindrome
assert sorted(solution.generatePalindromes("aabbc")) == ["abcba", "bacab"]  # one odd character allowed

# Multiple odd counts
assert solution.generatePalindromes("aaabbb") == []  # impossible due to two odd counts

# Larger repeated case
result = sorted(solution.generatePalindromes("aaaabbbb"))
expected = sorted([
    "aabbbbaa",
    "ababbaba",
    "abbaabba",
    "baabbaab",
    "babaabab",
    "bbaaaabb"
])
assert result == expected  # multiple valid unique palindromes

# Already a palindrome
assert sorted(solution.generatePalindromes("racecar")) == sorted(solution.generatePalindromes("racecar"))  # consistency check

# No duplicates in output
result = solution.generatePalindromes("aaaabb")
assert len(result) == len(set(result))  # uniqueness validation

Test	Why
"aabb"	Standard valid even-length palindrome case
"abc"	Multiple odd frequencies, impossible case
"a"	Minimum input size
"aaaa"	All characters identical
"aabbc"	Valid odd-length palindrome
"aaabbb"	Two odd counts should fail
"aaaabbbb"	Larger case with multiple permutations
"racecar"	Existing palindrome structure
"aaaabb"	Ensures duplicate avoidance

Edge Cases

One important edge case is when the input contains more than one odd-frequency character. For example, "abc" has three odd counts. A naive implementation might still attempt permutation generation, wasting computation time. The implemented solution detects this condition immediately and returns an empty list before any backtracking begins.

Another critical edge case is when all characters are identical, such as "aaaa". Without proper duplicate handling, backtracking could generate the same half permutation multiple times. The sorting step combined with the duplicate-skipping condition ensures that only one unique palindrome is produced.

A third important case is odd-length palindromes such as "aabbc". Exactly one character may appear an odd number of times, and it must occupy the center position. The implementation isolates this middle character before generating permutations, guaranteeing that every constructed palindrome maintains valid symmetry.

A subtle edge case involves duplicate characters in the half-string. For example, "aaaabb" produces half-string "aab". If duplicate skipping is implemented incorrectly, the algorithm may either generate duplicate palindromes or accidentally skip valid ones. The condition:

if i > 0 and half_chars[i] == half_chars[i - 1] and not used[i - 1]:

ensures that duplicates are skipped only within the same recursive layer, preserving correctness while eliminating repeated work.