# 266 Palindrome Permutation

Description

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

Example

Example1

`Input: s = "code"Output: FalseExplanation: No solution`

Example2

`Input: s = "aab"Output: TrueExplanation: "aab" --> "aba"`

Example3

`Input: s = "carerac"Output: TrueExplanation: "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:

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)

--

--

## More from Dhanarajappu

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.

## Get the Medium app

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.