Palindrome Permutation - Solution & Explanation

Problem Overview: Given a string s, determine whether any permutation of its characters can form a palindrome. A palindrome reads the same forward and backward, which imposes strict constraints on character frequencies.

A key observation: in a valid palindrome, every character must appear an even number of times except possibly one character in the center. That means the string can contain at most one character with an odd frequency.

Approach 1: Counting with Hash Table (O(n) time, O(1) space)

Count how many times each character appears using a hash table. Iterate through the string once and update the count for each character. After building the frequency map, iterate over the counts and track how many characters have odd frequencies.

If more than one character has an odd count, forming a palindrome is impossible. Otherwise, at least one permutation exists that arranges the characters symmetrically. The algorithm performs a single pass for counting and another small pass over the frequency map, resulting in O(n) time. Space is O(1) because the character set is bounded (for example ASCII).

This approach is straightforward and reliable. It demonstrates clear understanding of the palindrome property and uses constant-time lookups from a hash map. Problems involving character frequency analysis often use the same pattern across many string problems.

Approach 2: Bit Manipulation Toggle (O(n) time, O(1) space)

A more compact solution tracks odd/even counts using a bitmask. Instead of storing counts, toggle a bit corresponding to each character as you iterate through the string. If a character appears twice, its bit flips twice and returns to zero. At the end, the bitmask contains bits set only for characters with odd frequency.

A string can form a palindrome if the bitmask has either zero bits set or exactly one bit set. This can be checked using the expression mask & (mask - 1), which removes the lowest set bit. If the result is zero, at most one bit was set.

This technique reduces memory overhead and showcases efficient bit manipulation. It is particularly useful when the character set is small (like lowercase English letters).

Recommended for interviews: The hash table counting approach is what most interviewers expect first because it clearly communicates the palindrome frequency rule and runs in O(n) time with constant space. Mentioning the bitmask optimization afterward shows deeper understanding and comfort with low-level operations. Starting with counting proves correctness; following up with bit manipulation demonstrates strong problem-solving range.