Introduction
LeetCode 267: Palindrome Permutation II challenges you to generate all unique palindromic permutations of a given string.
This problem blends string manipulation with frequency counting and backtracking, and is an excellent way to test your understanding of palindromes and DFS.
Problem Statement
Given a string s, return all the palindromic permutations (without duplicates) of it.
If no palindrome can be formed, return an empty list.
Examples
python
Input: "aabb"
Output: ["abba", "baab"]
Input: "abc"
Output: []
✅ Step-by-Step Solution in Python
🔍 Step 1: Count Character Frequencies
A palindrome can only be formed if:
- At most one character has an odd count
- The rest must have even counts
We’ll store half of each character (since one half of the palindrome defines the other).
🔁 Step 2: Generate Half-Permutations
Use backtracking to generate all unique permutations of the left half of the palindrome.
🔄 Step 3: Mirror the Half
For each half-permutation:
- Mirror it to get the full palindrome
- If there’s a middle character (with odd count), insert it in the middle
✅ Python Code
python
from collections import Counter
def generatePalindromes(s: str) -> list[str]:
freq = Counter(s)
mid = ""
half = []
# Step 1: Check if palindrome is possible
odd_count = 0
for char, count in freq.items():
if count % 2 == 1:
odd_count += 1
mid = char
half.extend([char] * (count // 2))
if odd_count > 1:
return []
# Step 2: Backtrack to generate unique half permutations
res = []
used = [False] * len(half)
half.sort()
def backtrack(path):
if len(path) == len(half):
half_str = "".join(path)
full_palindrome = half_str + mid + half_str[::-1]
res.append(full_palindrome)
return
for i in range(len(half)):
if used[i]:
continue
if i > 0 and half[i] == half[i - 1] and not used[i - 1]:
continue
used[i] = True
backtrack(path + [half[i]])
used[i] = False
backtrack([])
return res
🧠 Explanation
Counter is used to count character frequencies- We collect half of each character for permutation
- Skip duplicates using backtracking logic with
used array
- Reconstruct the full palindrome by mirroring and inserting the middle character if any
🧪 Dry Run
Input: "aabb"
- Frequency:
{a: 2, b: 2} → all even → valid
- Half:
[a, b]
- Permutations:
["ab", "ba"]
- Result:
["abba", "baab"]
Input: "abc"
- Frequencies:
{a:1, b:1, c:1} → 3 odd → ❌ no palindrome → []
⏱️ Time and Space Complexity
- Time Complexity: O(n!) in worst case for permutations of half (n = len(s)/2)
- Space Complexity: O(n) for recursion + result list
✅ Conclusion
LeetCode 267: Palindrome Permutation II is a great challenge combining:
- Frequency counting
- Permutation generation
- String manipulation
You’ve learned how to:
- Check if a palindrome is possible
- Generate unique permutations
- Build full palindromes from halves