1.4 Palindrome Permutation – CCI

  • A palindrome will have duplicate characters on opposite sides except potentially the middle
  • get the count of characters
  • loop through the char count and return False if multiple characters have an odd count
  • could also keep track of odd counts while counting, but would have to check for each char
  • can also use a bit vector and map each char to pos 0-25
    • toggle on and off for each char
    • at the end, if permutation, will have only one True
    • if you get the value & value – 1, will be zero if there was only one True
# 1.4. Palindrom Permutation: Given a string, write a function to check 
# if it is a permutation of a palindrome. A palindrome is a word or
# phrase that is the same forwards and backwards. A permutation is a 
# rearrangement of letters. The palindrome does not need to be limited
# to just dictionary words.

# Input: Tact Coa
# Output: True

# Hash Table Solution
# Time complexity: O(n) count characters and then loop through smaller
# subset
# Space complexity: O(c) where c is each char / Also can be thought
# of as O(1) because set of characters is limited

# Bit Vector Solution
# Time complexity: O(n) need to look through each character
# Space complexity: O(1) information all stored in one integer

import unittest

def palindrome_permutation(s):
    char_count = get_char_count(s)
    odd_count = 0
    for char in char_count:
        if odd_count > 1:
            return False
        if char_count[char] % 2 == 1:
            odd_count += 1
    return True
def get_char_count(s):
    char_count = {}
    for char in s:
        if char not in char_count:
             char_count[char] = 1
            char_count[char] += 1
    return char_count
def palindrome_permutation2(s):
    bv = [0]*26
    for char in s:
       bv[array_index(char)] = 1^bv[array_index(char)]

    bit_str = [str(b) for b in bv]
    if int(''.join(bit_str),2) & int(''.join(bit_str),2) - 1:
        return False
        return True
def array_index(s):
    return ord(s.lower()) - 97
class Test(unittest.TestCase):
    def test_palindrome_permutation(self):
        # hash table solution

        # bit array solution
if __name__ == "__main__":