# Palindrome Permutation

## Problem Statement

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/characters.

The palindrome does not need to be limited to just dictionary words.

For example:

**input**:`Tact Coa`

**output**:`true`

(permutations:`tacocat`

,`atcocta`

,`actoact`

, etc.)

π‘ Assume that case is irrelevant, e.g.

`C`

and`c`

are the same character.

The solutions found in this article are adapted from Cracking The Coding Interview which provides code samples in Java.

## Solutions

To determine if a string is a permutation of a palindrome, we need to know if the characters can be arranged such that they can be written the same forwards and backwards.

In order to be able to write the characters the same forwards and backwards then we need to have an even number for all characters (when we have an even number of characters), or we can at **most** one character for which there is an odd number.

For instance:

Character | Count |
---|---|

`t` | `2` |

`a` | `2` |

`c` | `2` |

`o` | `1` |

We have 2 of all characters apart from `o`

. This means that we can rearrange the characters into a palindrome by balancing all the even numbered characters either side of the odd numbered character.

We can formulate rules for this:

- strings with an
**even**number of characters must have even counts for all characters - strings with an
**odd**number of characters must have*at most***one**character with an odd count

### Solution 1

A naΓ―ve solution would be to build up a hash table of all characters and their counts, e.g.:

```
public static bool IsPermutation(string input)
{
//create a dictionary of <char, int> to hold the count of each character
var table = new Dictionary<char, int>();
//iterate over the string and build the Dictionary<char, int>
foreach (var c in input)
{
//convert the character to its lowercase representation
var key = char.ToLower(c);
if (table.ContainsKey(key))
{
//the table contains this character already, so increment the count
table[key]++;
}
else
{
//the table doesn't yet contain this character, so add it with a count of 1
table[key] = 1;
}
}
//declare a temporary variable to tell us if we've found any odd counts yet
var foundOdd = false;
//loop through the table
foreach (var kv in table)
{
//if the count is an even number, skip this iteration
if (kv.Value % 2 == 0)
{
continue;
}
//if we've previously found an odd count, this cannot be a palindrome, so return 'false'
if (foundOdd)
{
return false;
}
//set foundOdd to 'true' - if we find _another_ odd count, this can't be a palindrome
foundOdd = true;
}
//if we get to here, then either all the characters have an even number of occurrences, or we only have a _single_ odd count
return true;
}
```

### Solution 2

I am **not** a Big O expert by *any* stretch of the imagination, but what we do know is that *any* algorithm will always need to visit every character in the input string. There’s little chance of us optimising the runtime of this algorithm, but we can clean it up.

A potential optimisation would be to check the odd counts as we build up the table, and then simply return at the end if we have more than 1 odd character:

```
public static bool IsPermutation(string input)
{
//create a variable to hold the count of odd numbered characters
var countOdd = 0;
//create the table as for solution 1
var table = new Dictionary<char, int>();
//iterate over each character in the input string
foreach (var c in input)
{
//conver the character to its lowercase representation
var key = char.ToLower(c);
if (table.ContainsKey(key))
{
//the character has been seen before, so increment its count by 1
table[key]++;
if (table[key] % 2 == 1)
{
countOdd++; //increment countOdd if we have an odd number of characters
}
else
{
countOdd--; //decrement countOdd if we don't have an odd number of characters
}
}
else
{
//we've not seen this character before, so add it to the table with a count of 1
table[key] = 1;
//we know we only currently have an odd number for this character, so increment countOdd by 1
countOdd++;
}
}
//finally, return true only if we have 0 or 1 odd counts
return countOdd <= 1;
}
```

## Solution 3

Technically, we don’t need to know the *count* of each character, we just need to know if the count of each character is odd or even.

We can therefore use a bit vector approach. When we encounter a character we map it to an integer and then toggle the bit at that character.

When we get to the end, we should have *at most* one bit set to 1.

```
public static bool Solution3(string input)
{
//start with a bitVector of zero
var bitVector = 0;
//loop through each char in the input string
foreach (var c in input)
{
//get the position in the alphabet of the current character
var x = GetCharacterNumber(c);
//toggle the bit in bitvector for this character
//i.e. if we're looking at 'a' and we've seen 'a' before, toggle 'a' to 0
//otherwise toggle 'a' to 1
bitVector = Toggle(bitVector, x);
}
//return true if either
//- bitvector is zero; OR
//- we have only a single bit set to 1
return bitVector == 0 || CheckExactlyOneBitSet(bitVector);
}
private static int GetCharacterNumber(char c)
{
//convert 'a' to its unicode representation
var a = Convert.ToInt32('a');
//convert 'z' to its unicode representation
var z = Convert.ToInt32('z');
//convert our input character (in lowercase!) to its unicode representation
var cVal = Convert.ToInt32(char.ToLower(c));
//check if our value is between a and z
if (a <= cVal && cVal <= z)
{
//if it is between a and c, calculate its position within the alphabet (from a to z)
return cVal - a;
}
//we don't have a valid character between 'a' and 'z', so return -1 as a default
return -1;
}
private static int Toggle(int vector, int index)
{
//check if the index value is less than zero
//if it is less then zero, then its outside the valid range
//we'll therefore just return the input value
if (index < 0)
{
return vector;
}
//here we create a bitmask on the index value by left-shifting the value 1 by the number of positions specified by index
//this effectively sets the bit at the index position to 1, leaving all other bits as zero
var mask = 1 << index;
//check if the bit at the index position in the vector is zero
//we use a bitwise AND operator between vector and mast
//if we get the result 0, this means that the bit at the index position is zero
if ((vector & mask) == 0)
{
//if the bit at the index position is zero, then we set the bit at the index position to 1
//we do this with the bitwise OR operator
vector |= mask;
}
else
{
//if the bit at the index position isn't zero, then we use the bitwise AND between the vector and the complement of mask (~mask)
//this clears the bit at the index position, setting it to zero
vector &= ~mask;
}
//this returns the modified vector
//if the bit at the index position was 1, it will now be zero.
//if the bit at the index position was 0, it will now be one.
return vector;
}
```

β οΈ Bit manipulation is not something I am as familiar with as I’d like, but the only way to learn is to do!

## Test Cases

The following test cases can be used to verify the solution(s):

```
public class PalindromePermutationTests
{
[TestCase("tactcoa", true)]
[TestCase("fish", false)]
[TestCase("racecar", true)]
[TestCase("a", true)]
[TestCase("ab", false)]
[TestCase("Tactcoa", true)]
public void TestIsPermutation(string input, bool expected)
{
var result = PalindromePermutation.IsPermutation(input);
Assert.That(result, Is.EqualTo(expected));
}
}
```

π‘ Whilst I prefer XUnit, sites like LeetCode tend to use NUnit in their online editors, so I’m making sure I’m keeping comfortable with NUnit.