current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

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();
    }
share|improve this question
    
I am not sure what you are trying to do, but to me your algorithm is plain wrong if I understand the problem correctly. Could you provide some test cases? –  tia Mar 28 at 15:41
    
I tried with several palindromes found online. e.g ROTAVATOR ->9,dad->3,malayalam->9 –  callee.args Mar 28 at 18:28
    
and the case where it fails? –  tia Mar 28 at 18:35
    
I'm not able to create one. :( –  callee.args Mar 28 at 18:37
    
Well, so what's the problem? –  tia Mar 28 at 18:40

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
I think above code is not correct. e.g. for kkkkk output is 3 instead of 5. for MALAYALAM output is 7 instead of 9. –  callee.args Mar 29 at 3:39
    
My bad. I fixed the bug already. –  tia Mar 29 at 3:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.