Longest palindrome in a given string using LINQ

Posted on

Problem

Problem:I need to write an algorithm that will return length of longest possible palindrome from a given string.

So if the input is aabbbccdfg
Program output should be 7. //–>[cabbbac]

Can someone point it out if there are any problems with below code?

public static void GetLongestPalindromeLength()
    {
        var input = Console.ReadLine().ToCharArray();
        var result = 0;
        var countsByChar = input.GroupBy(c => c);
        var oddCounts = countsByChar.Where(g => g.Count() % 2 != 0).Select(g => g.Count()).ToList();
        var evenCounts = countsByChar.Where(g => g.Count() % 2 == 0).Select(g => g.Count()).ToList();
        if (oddCounts.Any())
        {
            var max = oddCounts.Max();
            result += max;
            oddCounts.RemoveAt(oddCounts.FindIndex(e => e == max));
            result += evenCounts.Sum();
            result += oddCounts.Sum(e => e - 1);
        }
        else if (evenCounts.Any())
        {
           result += evenCounts.Sum();
        }
        Console.WriteLine(result);
        Console.ReadKey();
    }

Solution

Well, I think your algorithm is correct, but the code is quite bloat. Your code suggest that the longest palindrome size can be calculated by sum of n / 2 * 2 where n is the count of distinct alphabet that exists more than once in the string, and plus 1 if there are any “oddCounts”. So you can reduce the code to

    private static int GetLongestPalindrome(string value) {
        var map = value.GroupBy(c => c);
        int result = map.Sum(r => r.Count() / 2 * 2);
        if (map.Any(r => r.Count() % 2 != 0))
        {
            result++;
        }
        return result;
    }

n / 2 * 2 is the way to calculate for the nearest even number toward zero, and it equals to n - 1 where n is positive odd number.

Leave a Reply

Your email address will not be published. Required fields are marked *