# 266 Palindrome Permutation

Description

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

Example

**Example1**

`Input: s = "code"`

Output: False

Explanation:

No solution

**Example2**

`Input: s = "aab"`

Output: True

Explanation:

"aab" --> "aba"

**Example3**

`Input: s = "carerac"`

Output: True

Explanation:

"carerac" --> "carerac"

Approach 1:

*Using hashmap:*

For a string to be palindrome , it can at max have one character in it with odd number of occurrence and all other character need to occur even number of times. You can either use a list representing 128 ascii characters or a hashmap to store the count of each character.

`class Solution:`

def canPermutePalindrome(self, s):

cnt,total_odds=0,0

hash=dict()

for i in s:

if i in hash:

hash[i]+=1

else:

hash[i]=1

cnt+=1

print(cnt)

for i in hash:

total_odds+=hash[i]%2

return(total_odds<=1)

*Time :O(n)*

*Space: O(n)*

Approach 2:

*Further optimization to the loops used*

Instead of traversing the string and map . We can build a solution with just one loop , where we only traverse the entire string one time with a set to store the visited character in the string.

`class Solution:`

def canPermutePalindrome(self, s):

set_=set()

for i in s:

if i in set_:

set_.remove(i)

else:

set_.add(i)

return(len(set_)<=1)

*Time :O(n)*

*Space: O(n)*

Approach 3:

*Using Bit-masking*

We can optimize the solution using bit manipulation and bit masking. The same intuition that we followed in the approach 2 is used here . Assuming that when a character is found the bit at position having value = ascii value of character is set. If the character is found again the bit is cleared. Finally we check if the mask contain at most single 1.

`class Solution:`

def canPermutePalindrome(self, s):

mask=0

for c in s:

if (mask & 1<<ord(c) == 0):

mask|=1<<ord(c)

else:

mask&=~(1<<ord(c))

return(mask&(mask-1)==0)

*Time :O(n)*

*Space: O(1)*