Palindrome Permutation

Palindrome Permutation

What is this problem about?

The Palindrome Permutation problem asks whether any permutation of a given string can form a palindrome. A string can form a palindrome if and only if at most one character has an odd frequency. This easy coding problem tests character frequency analysis. The hash table, string, and bit manipulation interview pattern is the core.

Why is this asked in interviews?

Apple, Uber, Microsoft, Meta, Google, and Bloomberg ask this as a warm-up problem that tests the fundamental palindrome property — the character frequency rule. It can be solved with a hash map or a bitmask (XOR toggle for each character), demonstrating two levels of elegance.

Algorithmic pattern used

Frequency counting (or XOR bitmask). Count character frequencies. The string can form a palindrome iff at most one frequency is odd.

Bitmask approach: Maintain a 26-bit integer. For each character c, toggle bit c - 'a'. After all characters, count set bits: if ≤ 1, return true.

Example explanation

s="carrace". Frequencies: c=2, a=2, r=2, e=1. One odd frequency ('e'). Return true ("racecar" is a valid palindrome).

s="abcde". Frequencies: all 1. Five odd frequencies. Return false.

Bitmask: "carrace" → XOR toggles: final mask has only one bit set → true.

Common mistakes candidates make

• Checking if the string itself is a palindrome (not what's asked).
• Counting characters incorrectly with uppercase/lowercase confusion.
• Off-by-one: "at most one odd" means 0 or 1, not exactly 1.
• Not handling even-length strings (they need exactly 0 odd frequencies).

Interview preparation tip

Palindrome Permutation and Palindrome Number are the two foundational palindrome problems. The frequency rule — at most one character with odd count — is the key palindrome property for permutations. The bitmask approach using XOR toggle is elegant: mask ^= (1 << (c - 'a')). After processing, popcount(mask) <= 1. Practice both hash map and bitmask approaches.