# Palindrome Permutation

## Problem

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

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MR0vhcwu7270PpYAHRL%2F-MR11_KUD2Rf8n83xc_i%2FScreen%20Shot%202021-01-14%20at%2010.56.04%20AM.png?alt=media\&token=8e1e2e49-5e9d-4977-833c-19a8e71f9155)

### 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