Palindrome Permutation
A unique way to solve this interview question in O(N) time
Question: Given a string, write a function to check if it is a permutation of a palindrome.
At first glance, this question is very straightforward. Maintain a counter of the frequencies of all the alphabets in the string and at last, check if the counter is odd for at most one alphabet.
But on a different thought, do we really need to maintain a counter? Can we do without a counter?
Yes. Let’s see how.
We only need to check if the occurrence of every element is odd or even. 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.
Similarly, we can use a bit vector, where every position of that bit vector maps to a single alphabet. When we see any alphabet in the string, we toggle the corresponding bit in the bit vector.
At last, we only check if the remaining bit vector is 0 or is a power of 2. If it is then the string is a permutation of a palindrome otherwise not.
