String Algorithm - Program To Validate Given String A Palindrome Permutation

Problem Statement

 

Write a program to check if the given string is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backward. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words. You need to consider that comparison is case insensitive, whitespace is non-significant and all the non-letter characters.

 

Example 1

 

Input: s1 = "mama d"

 

Output: Palindrome Permutation (permutation: madam)

 

Explanation: there are 5 non-letter characters in the given string "mama d" and this is a permutation of a palindrome because it has two M, two A, one d. Strings of an odd length must have exactly one character with an odd count.

 

Example 2

 

Input: s1 = "Tic Toe"

 

Output: No Palindrome Permutation

 

Explanation: there are 6 non-letter characters in the given string "Tic Toe" and this is not a permutation of a palindrome because it has two T, One C, One O One E, One I (more than one character with odd count)

 

Solution

 

Look at the steps described for an algorithm

• Convert the given string into an array of type character
• Declare an array of integer type with size 128 that maps the ASCII value because as per the ASCII standard character set there are 128 characters for electronic communication.
• Iterate through an array and for the index matching with the character ASCII value, set the value in the integer array to 1 if the value is 0 otherwise set the value in the integer array to 0 if it is already 1

Check that no more than one character has an odd count in the integer character set. If more than one characters with odd count is found, then return failure signal and print the result “No Palindrome Permutation” otherwise “Palindrome Permutation”

class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Please enter string to be processed: ");
            var inputString = Console.ReadLine();
            var characterSetMappingTable = PrepareCharacterSetMappingTable(inputString);
            bool isOnlyOddOneFound = IsOnlyOddOneFound(characterSetMappingTable);
            Console.WriteLine(isOnlyOddOneFound ? "Palindrome Permutation" : "No Palindrome Permutation");

            Console.ReadLine();
        }

        private static int[] PrepareCharacterSetMappingTable(string inputString)
        {
            string stringToBeProcessed = inputString.Replace(" ", "").ToLower();
            //Convert string into an array f characters
            char[] chars = stringToBeProcessed.ToCharArray();
            //declare an array of integer type with size 128 because as per the ASCII standard character set
            //there are 128 characters for electronic communication.
            int[] characterSetMappingTable = new int[128];

            //Iterate through an array and for the index matching with the character ASCII value,
            //set the value in the integer array to 1 if the value is 0 otherwise set the value  in the integer array to 0 if it is already 1
            foreach (char c in chars)
            {
                var characterIndex = (int)c;

                if (characterSetMappingTable[characterIndex] == 0)
                    characterSetMappingTable[characterIndex] = 1;
                else if (characterSetMappingTable[characterIndex] == 1)
                    characterSetMappingTable[characterIndex] = 0;
            }

            return characterSetMappingTable;
        }

        /// <summary>
        /// this method will determine that no more than one character has an odd count.
        /// </summary>
        /// <param name="characterSetMappingTable"></param>
        /// <returns></returns>
        private static bool IsOnlyOddOneFound(int[] characterSetMappingTable)
        {
            int countOddOneFound = 0;

            foreach (var index in characterSetMappingTable)
            {
                if (countOddOneFound > 1)
                    return false;
                if (index == 1)
                {
                    countOddOneFound++;
                }
            }

            return true;
        }
    }

Time Complexity

 

O(n )

 

array iteration takes O(n) time to iterate through n characters where n is the length of the string.

 

Note
Please feel free to propose or suggest a solution you might think can be followed to make it better and more optimized.