Given a string, find out if any anagram of a given string is a palindrome. For example, “AABBC” has an anagram “ABCBA” which is a palindrome.
The brute force solution will be to find all anagrams of string and then check each one if that is a palindrome. For N character long string, we will have n! anagrams, and checking each one of that for palindrome will be a 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 the same characters as the second half. In the case of odd length string, we can safely ignore the middle character.
In other terms, each character should occur even a number of times except one which is a middle character that may occur an odd number of times. Best way to check if the 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 an odd number of occurrence.
Extending the same idea from the previous post: we will be using a hash table and increment- decrement the corresponding count of character in the hash. In the end, we will sum the array and if the sum of the array is greater than 1, then we cannot have any anagram which will be palindrome else at least anagram of the string will be a palindrome.
The complexity of above code is O(N) with a constant amount of memory required.