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)

--

--

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

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Dhanarajappu

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