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 means most characters must appear an even number of times.

The key property of palindromes: every character appears an even number of times except possibly one character (the middle character in odd-length palindromes). The solution reduces to checking how many characters have odd frequencies.

Approach 1: Sort and Count Adjacent Characters (O(n log n) time, O(1) extra space)

Sort the string first so identical characters appear next to each other. Then iterate through the sorted characters and count how many times each character appears. Track how many groups have an odd count. If more than one character has an odd frequency, a palindrome permutation is impossible. Sorting dominates the complexity at O(n log n), while the scan itself is linear. This approach is simple but inefficient compared to hash-based solutions.

Approach 2: Hash Set Toggle (O(n) time, O(k) space)

Iterate through the string and maintain a set of characters with odd counts. When you see a character, toggle it in the set: if it already exists, remove it; otherwise insert it. At the end, the set contains only characters that appeared an odd number of times. A palindrome permutation is possible if the set size is at most one. Each step performs constant-time hash operations, giving O(n) time and O(k) space where k is the number of distinct characters. This approach relies on a Hash Table concept and works well for general strings.

Approach 3: Bit Vector for Character Parity (O(n) time, O(1) space)

If the string contains only lowercase letters, you can compress the parity check into a single integer bitmask. Each bit represents whether a character count is currently odd or even. For each character, flip its corresponding bit using XOR. After processing the entire string, check whether the bitmask has at most one bit set. That condition can be tested with x & (x - 1). This approach uses Bit Manipulation to store frequency parity efficiently and keeps space constant.

All solutions rely on the same insight: a valid palindrome permutation allows at most one odd-frequency character. The difference lies in how efficiently you track character parity across the string.

Recommended for interviews: The hash-set parity approach is the most common interview solution because it’s easy to explain and runs in O(n) time. Mentioning the bitmask optimization shows deeper understanding and strong familiarity with bit manipulation patterns.