Often in our group we discuss about puzzles or problems related to data structure and algorithms. One such day, we discussed about:
how will we find if any anagram of a string is palindrome or not?
Our first thought went in the direction to start from first character and then traverse till end to see if there could be matching pair. Keep track of it, move to next character till middle and then stitch all to figure if so. It solves, but the query was – could it be solved better though?
Of course! With putting some stress on the brain, it turned out that in a single read, we will have info enough, to tell, if any anagram formed from the input string can be a palindrome or not.
Thought converted to Code
static void CheckIfStringAnagramHasPalindrome()
{
Console.WriteLine($"Please enter a string:");
// Ignore casing
var inputString = Console.ReadLine().ToLower();
// Just need to keep track of unique characters
var characterSet = new HashSet<char>();
// Single traversal of input string
for(int i=0; i<inputString.Length; i++)
{
char currentCharacter = inputString[i];
if(characterSet.Contains(currentCharacter))
characterSet.Remove(currentCharacter);
else
characterSet.Add(currentCharacter);
}
// Character counts in set will help
// identify if palindrome possible
var leftChars = characterSet.Count;
if(leftChars == 0 || leftChars == 1)
Console.WriteLine($"YES - possible.");
else
Console.WriteLine($"NO - Not possible.");
}
Approach looked good, as with a single traversal and usage of HashSet, i.e. with overall Order of Time complexity O(n) & Space complexity O(1), we were able to solve it.
It was fun solving!