Palindrome Permutation II solution and explanation
7 more videos on this problem
LeetCode 267. Palindrome Permutation II Explanation and Solutionhappygirlzt · 8:00 · 3K views
LeetCode 267. Palindrome Permutation II 中文解释 Chinese Versionhappygirlzt · 8:26 · 1K views
267. Palindrome Permutation II (Leetcode Medium)Programming Live with Larry · 14:27 · 403 views
Leetcode 267 Palindrome Permutation IIAlgorithmicIQ · 22:14 · 335 views
Leetcode 267. Palindrome Permutation II (backtracking)LetsCode · 15:32 · 292 views
Palindrome Permutation II (Medium), C++, LeetcodeH William Polenz · 50:49 · 124 views
LeetCode Medium: 267. Palindrome Permutation IIrobzingcod · 7:33 · 89 views
LeetCode 267: Palindrome Permutation IIAlitaCode · 27:36 · 3 views
The problem
Given a string s, return all the palindromic permutations (without duplicates) of it.
You may return the answer in any order. If s has no palindromic permutation, return an empty list.
Example 1:
Input: s = "aabb" Output: ["abba","baab"]
Example 2:
Input: s = "abc" Output: []
Constraints:
1 <= s.length <= 16sconsists of only lowercase English letters.
Approach overview
Problem Overview: Given a string s, generate all unique permutations that form a palindrome. If no palindromic arrangement exists, return an empty list. The challenge is detecting whether a palindrome is possible and avoiding duplicate permutations.
Approach 1: Generate All Permutations + Palindrome Check (Brute Force) (Time: O(n! * n), Space: O(n))
This method generates every permutation of the string and checks whether each permutation is a palindrome. Use standard permutation generation with recursion or backtracking, then verify the result using a two-pointer palindrome check. The drawback is factorial growth: n! permutations are generated even though only a tiny subset could be valid palindromes. Duplicate permutations also appear when characters repeat, which requires additional filtering using a set. This approach works only for very small strings and mainly demonstrates baseline reasoning.
Approach 2: Hash Map + Half Permutation Backtracking (Time: O((n/2)!), Space: O(n))
A palindrome is symmetric. At most one character can appear an odd number of times. Start by counting character frequencies using a hash table. If more than one character has an odd frequency, forming a palindrome is impossible. Otherwise, build a half string containing freq[c] / 2 copies of each character. The center character (if any) is the one with the odd count.
Next, generate unique permutations of this half string using backtracking. Sorting or using a visited array prevents duplicate permutations when characters repeat. For every generated half permutation, construct the palindrome as half + middle + reverse(half). Because only half of the characters are permuted, the search space drops from n! to (n/2)!, which is dramatically smaller.
This method leverages symmetry and frequency counting to prune invalid cases early. The main operations are counting characters, recursively generating permutations of the half string, and mirroring it using simple string manipulation. Memory usage remains linear because only the recursion stack and frequency structures are stored.
Recommended for interviews: Interviewers expect the hash map + half-permutation backtracking solution. Recognizing the palindrome property (only one odd frequency allowed) shows strong problem decomposition. Mentioning the brute force permutation approach first shows understanding of the search space, but the optimized half-generation technique demonstrates algorithmic insight and practical efficiency.
Solution
class Solution:
def generatePalindromes(self, s: str) -> List[str]:
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
cnt = Counter(s)
mid = ''
for c, v in cnt.items():
if v & 1:
if mid:
return []
mid = c
cnt[c] -= 1
ans = []
dfs(mid)
return ansclass Solution {
private List<String> ans = new ArrayList<>();
private int[] cnt = new int[26];
private int n;
public List<String> generatePalindromes(String s) {
n = s.length();
for (char c : s.toCharArray()) {
++cnt[c - 'a'];
}
String mid = "";
for (int i = 0; i < 26; ++i) {
if (cnt[i] % 2 == 1) {
if (!"".equals(mid)) {
return ans;
}
mid = String.valueOf((char) (i + 'a'));
}
}
dfs(mid);
return ans;
}
private void dfs(String t) {
if (t.length() == n) {
ans.add(t);
return;
}
for (int i = 0; i < 26; ++i) {
if (cnt[i] > 1) {
String c = String.valueOf((char) (i + 'a'));
cnt[i] -= 2;
dfs(c + t + c);
cnt[i] += 2;
}
}
}
}class Solution {
public:
int n;
vector<string> ans;
unordered_map<char, int> cnt;
vector<string> generatePalindromes(string s) {
n = s.size();
for (char c : s) ++cnt[c];
string mid = "";
for (auto& [k, v] : cnt) {
if (v & 1) {
if (mid != "") {
return ans;
}
mid += k;
}
}
dfs(mid);
return ans;
}
void dfs(string t) {
if (t.size() == n) {
ans.push_back(t);
return;
}
for (auto& [k, v] : cnt) {
if (v > 1) {
v -= 2;
dfs(k + t + k);
v += 2;
}
}
}
};func generatePalindromes(s string) []string {
cnt := map[byte]int{}
for i := range s {
cnt[s[i]]++
}
mid := ""
ans := []string{}
for k, v := range cnt {
if v%2 == 1 {
if mid != "" {
return ans
}
mid = string(k)
}
}
var dfs func(t string)
dfs = func(t string) {
if len(t) == len(s) {
ans = append(ans, t)
return
}
for k, v := range cnt {
if v > 1 {
cnt[k] -= 2
c := string(k)
dfs(c + t + c)
cnt[k] += 2
}
}
}
dfs(mid)
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Generate All Permutations + Palindrome Check | O(n! * n) | O(n) | Conceptual baseline or very small strings |
| Hash Map + Half Permutation Backtracking | O((n/2)!) | O(n) | General case; optimal solution for interviews and large inputs |
Frequently asked questions
Is Palindrome Permutation II easy or hard?
Palindrome Permutation II is generally rated Medium difficulty. The challenge lies in recognizing the palindrome frequency property and reducing the permutation search space by generating only half of the string.
Palindrome Permutation II Python/Java solution
Typical implementations use a hash map to count characters, build a half-string list, and apply backtracking with a visited array to avoid duplicates. After generating a half permutation, the algorithm concatenates it with an optional middle character and the reversed half to produce a full palindrome.
How to solve Palindrome Permutation II in O(n)?
O(n) time is achievable only for the feasibility check, not for generating all palindromes. Counting character frequencies with a hash map and verifying that at most one character has an odd count takes O(n). Generating all valid permutations afterward requires factorial time relative to half the string length.
What is the best approach for Palindrome Permutation II?
The most efficient method counts character frequencies using a hash map, verifies that at most one character has an odd count, then generates permutations of only half the string using backtracking. Each half permutation is mirrored to form a full palindrome. This reduces the search space from n! permutations to roughly (n/2)! permutations.
Is Palindrome Permutation II asked at Google/Amazon/Meta?
Palindrome permutation and backtracking problems frequently appear in interviews at large tech companies including Google, Amazon, and Meta. Variations test understanding of character frequency counting, pruning invalid states, and generating unique permutations efficiently.
What data structure is used in Palindrome Permutation II?
A hash table (or frequency array) is used to count character occurrences. Backtracking with recursion generates unique permutations of half the string, and basic string operations mirror the result to form palindromes.
What is the time complexity of Palindrome Permutation II?
The optimized solution runs in O((n/2)!) time because only half of the characters are permuted. Building each palindrome takes O(n) time, but the dominant factor is the number of half permutations generated by backtracking. Space complexity is O(n) for recursion and result construction.