Palindrome Permutation

Problem

Given a string, determine if a permutation of the string could form a palindrome.

Thought Process

• All letters must occur in pairs with the exception of odd length strings which can at most have one letter that is not a pair

Solution

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        ss = set()
        
        for letter in s:
            if letter not in ss:
                ss.add(letter)
            else:
                ss.remove(letter)
        if len(ss) > 1:
            return False
        return True

Time Complexity

• Time: O(n)

• Space: O(1) because hash set is bounded by 26 characters