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)