Length of Longest Palindrome

Problem: Given a string return the length of the longest palindrome that can be built with the characters in the input string.

Example:

Input: s = "abcdd"
Output: 3
Explanation:
Longest palindromes that can be built are "dad", "dbd" or "dcd" and the length of these strings are 3.

Approach: It looks like a straight forward problem. First we get the count of all the characters and say we stored in a hash with key as character and frequency of that character as value.

Now we iterate through the above generated hash and see if the count of character is even or odd.

• If count is even, just add it to the result. "dd", "cccc" etc. always form palindrome even if they are merged together with other palindromes.
• If count is odd, then we can add count - 1 in the result and we memorize that there was a character which occurred odd number of times.
• If there was any character with odd frequency then add 1 to the final result. Look at the strings: "dd", "ccc", "bbb". The longest palindromes could be "dbcccbd" or "dcbbbcd" or some other palindrome permutation of the same but the key is either b or c can come 3 times.

That's all!

Implementation in C#:

        public int LongestPalindrome(string s)

        {

            Dictionary<char, int> frequencies = new Dictionary<char, int>();

            foreach(char ch in s)

            {

                if (!frequencies.ContainsKey(ch))

                {

                    frequencies.Add(ch, 0);

                }

                ++frequencies[ch];

            }

            int longestPalindrome = 0;

            bool shouldAddOne = false;

            foreach(char ch in frequencies.Keys)

            {

                if (frequencies[ch] % 2 == 0)

                {

                    longestPalindrome += frequencies[ch];

                }

                else

                {

                    longestPalindrome += frequencies[ch] - 1;

                    shouldAddOne = true;

                }

            }

            return shouldAddOne ? longestPalindrome + 1 : longestPalindrome;

        }

Complexity: O(n)