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.

Description Hints 2 Solution Video 8:00

267. Palindrome Permutation II

Medium41.9% acceptancePremium elsewhere, free here

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 <= 16
s consists of only lowercase English letters.

Topics

Hints open one at a time

Hint 1

If a palindromic permutation exists, we just need to generate the first half of the string.

Hint 2

To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II or Next Permutation.

8:00

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

267. Palindrome Permutation II

Topics

Hints open one at a time

Similar problems