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.
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.
Complexity of above code is O(N) with constant amount of memory required.