Strings : Find if any anagram of string is palindrome.

Find if any anagram of string is palindrome

Given a string, find out if any anagram of given string is palindrome.
For example, “AABBC” has an anagram “ABCBA” which is palindrome.

Analysis

Brute force solution will be to find all anagrams of string and then check each one if that is palindrome. For N character long string, we will have n! anagrams and checking each one of that for palindrome will be computation intensive task, so not a good solution.
What is required for a string to be palindrome string?
We need first half of the string to contain same characters as second half. In case of odd length string we can safely ignore the middle character.
In other terms, each character should occur even number of time except one which is middle character which may occur odd number of times.
Best way to check if character occurs even number of times is to increment to count when it is zero and decrement when it is 1.If at the end we have count corresponding to that character as zero, that means we have even number of occurrence of this character, if not then we have odd number of occurrence.
Extending the same idea from previous post: we will be using a hash table and increment- decrement corresponding count of character in hash.
At the end we will sum the array and if sum of array is greater than 1, then we cannot have any anagram which will be palindrome else at least anagram of string will be palindrome.

Code

Complexity of above code is O(N) with constant amount of memory required.

  • try

    what will you do when size of link list is unknown ie number of nodes is not given to us.

    • http://algorithmsandme.in/ Jitendra Sangar

      We don’t need to know number of nodes. We are finding the middle element by hare and tortoise algorithm.

  • jammy

    Third way is to reverse the linked list till the middle node, and then starting from middle node, move in opposite direction comparing each node. If any of the node differ, return false. If we reach at head and tail of the list, then linked list is palindrome. Once done, reverse the half linked list again and restore the original list.

    What does bold part means?a small example wud be enough.

  • are you sure

    Use a recursive function. Pass front pts as another argument. When at the end of list, check if front ptr data equals last recursive node. Forward the front ptr and continue the check. No need to reverse or stack etc. One can optimize further to stop recursive calls in middle.