LeetCode 266: Palindrome Permutation - Complete Solutions Guide

Problem Statement

Given a string s, determine if a permutation of the string could form a palindrome. Return true if it can, false otherwise.

Copy codeInput: s = "code"
Output: false
Explanation: No permutation of "code" can form a palindrome

Input: s = "aab"
Output: true
Explanation: "aba" is a valid palindrome permutation

Solution 1: Hash Map Counting

Explanation

Count character frequencies using a dictionary: 1. Count Characters: Track each character's occurrence 2. Check Counts: At most one character can have odd count 3. Return Result: Based on odd count condition

Step-by-Step Example

For s = "aab": 1. Counts: {'a':2, 'b':1} 2. Only 'b' has odd count → true

For s = "code": 1. Counts: {'c':1, 'o':1, 'd':1, 'e':1} 2. Four odd counts → false

Python Code

Copy codefrom collections import defaultdict

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        freq = defaultdict(int)
        for char in s:
            freq[char] += 1

        odd_count = 0
        for count in freq.values():
            if count % 2 != 0:
                odd_count += 1
            if odd_count > 1:
                return False
        return True

Complexity

• Time: O(n) - Single pass through string
• Space: O(1) - Fixed space for alphabet (26 letters)
• Pros: Easy to understand and implement

Solution 2: Array Counting (Optimal for Lowercase)

Explanation

Use fixed-size array for lowercase English letters: 1. Initialize Array: Size 26 for a-z 2. Count Characters: Increment corresponding index 3. Check Odd Counts: Same as hash map approach

Python Code

Copy codeclass Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        counts = [0] * 26
        for char in s:
            counts[ord(char) - ord('a')] += 1

        odd_count = 0
        for count in counts:
            if count % 2 != 0:
                odd_count += 1
            if odd_count > 1:
                return False
        return True

Complexity

• Time: O(n) - Same as Solution 1
• Space: O(1) - Fixed 26-element array
• Why Better: More efficient than hash map for limited alphabet

Solution 3: Bit Masking (Most Space Efficient)

Explanation

Use bitmask to track odd/even counts: 1. Bitmask: Each bit represents a character's count parity 2. Toggle Bits: Flip bit for each character 3. Check Mask: At most one bit set (power of two check)

Step-by-Step Example

For s = "aab": 1. Initial mask: 0 2. 'a' → mask ^= 1 → 1 3. 'a' → mask ^= 1 → 0 4. 'b' → mask ^= 2 → 2 5. Final mask: 2 (10 in binary) → only one bit set → true

Python Code

Copy codeclass Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        mask = 0
        for char in s:
            mask ^= 1 << (ord(char) - ord('a'))
        return mask & (mask - 1) == 0

Complexity

• Time: O(n) - Single pass through string
• Space: O(1) - Single integer storage
• Why Best: Minimal space usage with bit operations

Key Insight

The bitmask approach efficiently tracks character parity (odd/even) using XOR operations. A palindrome permutation will result in a mask with at most one bit set.

Edge Cases to Consider

1. Empty string: Considered valid (vacuous palindrome)
2. Single character: Always valid
3. All even counts: Valid palindrome
4. One odd count: Valid for odd-length palindrome
5. Multiple odd counts: Invalid

Final Thoughts

• Interview Tip: Bitmask solution demonstrates advanced skills
• Key Insight: Character count parity determines palindrome possibility
• Follow-up: How would you handle Unicode characters?