1
\$\begingroup\$

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();
    }
\$\endgroup\$
6
  • \$\begingroup\$ 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? \$\endgroup\$ – tia Mar 28 '15 at 15:41
  • \$\begingroup\$ I tried with several palindromes found online. e.g ROTAVATOR ->9,dad->3,malayalam->9 \$\endgroup\$ – callee.args Mar 28 '15 at 18:28
  • \$\begingroup\$ and the case where it fails? \$\endgroup\$ – tia Mar 28 '15 at 18:35
  • \$\begingroup\$ I'm not able to create one. :( \$\endgroup\$ – callee.args Mar 28 '15 at 18:37
  • \$\begingroup\$ Well, so what's the problem? \$\endgroup\$ – tia Mar 28 '15 at 18:40
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$ – callee.args Mar 29 '15 at 3:39
  • \$\begingroup\$ My bad. I fixed the bug already. \$\endgroup\$ – tia Mar 29 '15 at 3:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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