Palindrome Permutation

String, Bits Approach

You are given a string 'S', check if there exists any permutation of the given string that is a palindrome.

• A palindrome is a word or phrase that reads the same from forward and backward e.g. “aba”, it reads the same from forward and backward.

• A permutation is a rearrangement of letters.

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

Solutions

A palindrome is a string that is the same forwards and backwards. Therefore, to decide if a string is a permutation of a palindrome, we need to know if it can be written such that it's the same forwards and backwards.

What does it take to be able to write a set of characters the same way forwards and backwards? We need to have an even number of almost all characters, so that half can be on one side and half can be on the other side. At most one character (the middle character) can have an odd count.

For example, we know tactcoapapa is a permutation of a palindrome because it has two Ts, four As, two Cs, two Ps, and one 0. That O would be the center of all possible palindromes.

Approach – Using hash table

Implementing this algorithm is fairly straightforward. We use a hash table to count how many times each character appears. Then, we iterate through the hash table and ensure that no more than one character has an odd count.

Steps

1. First check if string is null. if string is null, then return string.

2. Run loop for each character of string and add it's count into hash table and count odd occurrence ( count % 2 == 1).

3. If odd occurrence is less than and equal to one, then string is palindrome else not.

   public bool IsPermutationOfPalindrome(string str)
    {
        if (str is null)
            return true;

        int countOdd = 0;
        var table = new Dictionary<int, int>();
        foreach (char item in str!)
        {
            int x = Char.ToLower(item);
            if (!table.ContainsKey(x))
            {
                table.Add(x, 1);
            }
            else
            {
                table[x]++;
            }

            if (table[x] % 2 == 1)
            {
                countOdd++;

            }
            else
            {
                countOdd--;
            }
        }
        return countOdd <= 1;
    }

Note: Here, we made all character to lower case to make it case insensitive.

Complexity

• Time Complexity: O(n)

• Auxiliary Space: O(n)

Approach – Using bit vector

If you think more deeply about this problem, you might notice that we don't actually need to know the counts. We just need to know if the count is even or odd. Think about flipping a light on/off (that is initially off). If the light winds up in the off state, we don't know how many times we flipped it, but we do know it was an even count.

Given this, we can use a single integer (as a bit vector). When we see a letter, we map it to an integer between O and 26 (assuming an English alphabet). Then we toggle the bit at that value. At the end of the iteration, we check that at most one bit in the integer is set to 1.

We can easily check that no bits in the integer are 1: just compare the integer to 0. There is actually a very elegant way to check that an integer has exactly one bit set to 1.

An integer like 00010000. We could of course shift the integer repeatedly to check that there's only a single 1. Alternatively, if we subtract 1 from the number, we'll get 00001111. What's notable about this is that there is no overlap between the numbers (as opposed to say 00101000, which, when we subtract 1 from, we get 00100111.) So, we can check to see that a number has exactly one 1 because if we subtract 1 from it and then AND it with the new number, we should get 0.

image

Steps

1. First check if string is null. if string is null, then return string.

2. Run loop for each character of string and add toggle each bit.

3. Check bit vector value is zero or bitwise and of bit vector with subtract one from bit vector is zero.

   public bool IsPermutationOfPalindrome(string str)
    {
        int bitVactor = CreateBitVactor(str);

        return bitVactor == 0 || (bitVactor & (bitVactor - 1)) == 0;
    }

    private int CreateBitVactor(string str)
    {
        int bitVactor = 0;
        foreach (char item in str)
        {
            bitVactor = Toggle(bitVactor, item);
        }
        return bitVactor;
    }
    private int Toggle(int bitVactor, int index)
    {
        if (index < 0)
        {
            return bitVactor;
        }

        int mask = 1 << index;

        if ((bitVactor & mask) == 0)
        {
            bitVactor |= mask;
        }
        else
        {
            bitVactor &= ~mask;
        }
        return bitVactor;
    }

Complexity

• Time Complexity: O(n)

• Auxiliary Space: O(1)