Palindrome Permutation — October 12, 2026

Given a string s, determine if it is a permutation of a palindrome. This means the characters of s can be rearranged to form a palindrome.

• Case-insensitive: 'A' is considered the same as 'a'.
• Ignore non-alphanumeric characters: Spaces, punctuation, etc., should be disregarded.

Example:

Input: "Tact Coa"
Output: true
Explanation: Permutations include "taco cat", "atco cta".

Solution

Approach:

• Palindrome Property: A string can be a permutation of a palindrome if, at most, one character appears an odd number of times. All other characters must appear an even number of times.
• Character Counting: Iterate through the input string.
  • Convert each character to lowercase.
  • Only consider alphanumeric characters.
  • Use a hash map (or frequency array) to store the count of each valid character.
• Odd Count Check: After counting all characters, iterate through the character counts.
  • Maintain a counter for characters with an odd frequency.
  • If this counter exceeds 1 at any point, it's impossible to form a palindrome, so return false.
• Final Result: If the loop completes (meaning 0 or 1 character had an odd frequency), return true.

Python Solution:

def canPermutePalindrome(s: str) -> bool:
    counts = {}
    for char in s:
        # Process only alphanumeric characters and convert to lowercase
        if 'a' <= char.lower() <= 'z':
            c = char.lower()
            counts[c] = counts.get(c, 0) + 1

    odd_counts = 0
    for count in counts.values():
        if count % 2 != 0:
            odd_counts += 1
        # If more than one character has an odd count, it cannot form a palindrome
        if odd_counts > 1:
            return False
            
    # If 0 or 1 character has an odd count, it can form a palindrome
    return True