[LeetCode] Palindrome Permutation I

Problem: Given a string, determine if a permutation of the string could form a palindrome.

Example:

Input: "code"
Output: False

Input: "aab"
Output: True

Input: "carerac"
Output: True

Approach: This is an easy problem to solve. If you see to be a palindrome string of even length the frequency of each character must be even. In case of odd length palindrome, we can easily observe that except one character, every other character in the string must occur even times.

Implementation in C#:

    public static bool CanPermutePalindrome(string s) 

    {

        HashSet<char> charSet = new HashSet<char>();        

        foreach (char ch in s)

        {

            if (charSet.Contains(ch))

            {

                charSet.Remove(ch);

            }

            else

            {

                charSet.Add(ch);

            }

        }

        return charSet.Count <= 1;

    }

Complexity: O(n)