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.

Here is the question: find the largest palindrome from a string.

Ex:

ABCBAHELLOHOWRACECARAREYOUILOVEUEVOLIIAMAIDOINGGOOD

Result:

ILOVEUEVOLI

I am not sure of the efficiency of the algorithm.

static void Main(string[] args)
{
    var str = "ABCBAHELLOHOWRACECARAREYOUILOVEUEVOLIIAMAIDOINGGOOD";
    var longestPalindrome = GetLongestPalindrome(str);
    Console.WriteLine(longestPalindrome);
    Console.Read();
}

private static string GetLongestPalindrome(string input)
{
    int rightIndex = 0, leftIndex = 0;
    List<string> paliList = new List<string>();
    string currentPalindrome = string.Empty;
    string longestPalindrome = string.Empty;
    for (int currentIndex = 1; currentIndex < input.Length - 1; currentIndex++)
    {
        leftIndex = currentIndex - 1;
        rightIndex = currentIndex + 1;
        while (leftIndex >= 0 && rightIndex < input.Length)
        {
            if (input[leftIndex] != input[rightIndex])
            {
                break;
            }
            currentPalindrome = input.Substring(leftIndex, rightIndex - leftIndex + 1);
            paliList.Add(currentPalindrome);
            leftIndex--;
            rightIndex++;
        } 
    }
    var x = (from c in paliList
             select c).OrderByDescending(w => w.Length).First();
    return x; 
}
share|improve this question

3 Answers 3

up vote 10 down vote accepted

Your basic algorithm seems pretty efficient, but building a list then sorting it just to find the longest one isn't very efficient. It would be much more efficient to just keep track of the longest palindrome:

    private static string GetLongestPalindrome(string input)
    {
        int rightIndex = 0, leftIndex = 0;
        var x = "";
        string currentPalindrome = string.Empty;
        string longestPalindrome = string.Empty;
        for(int currentIndex = 1; currentIndex < input.Length - 1; currentIndex++)
        {
            leftIndex = currentIndex - 1;
            rightIndex = currentIndex + 1;
            while(leftIndex >= 0 && rightIndex < input.Length)
            {
                if(input[leftIndex] != input[rightIndex])
                {
                    break;
                }
                currentPalindrome = input.Substring(leftIndex, rightIndex - leftIndex + 1);
                if(currentPalindrome.Length > x.Length)
                    x = currentPalindrome;
                leftIndex--;
                rightIndex++;
            }
        }
        return x;
    }

In my tests this is 3 times faster.

I hate to break this to you, but there is a bug in your code, which will probably mean rewriting your algorithm. You algorithm assumes that the palindrome will be an odd number of characters. However, a palindrome can be an even number of characters and your code won't find it if it is.

Here's some code that will find the longest palindrome regardless:

    static string LargestPalindrome(string input)
    {
        string output = "";
        int minimum = 3;
        for(int i = 0; i < input.Length - minimum; i++)
        {
            for(int j = i + minimum; j < input.Length - minimum; j++)
            {
                string forstr = input.Substring(i, j - i);
                string revstr = new string(forstr.Reverse().ToArray());
                if(forstr == revstr && forstr.Length > minimum)
                {
                    output = forstr;
                    minimum = forstr.Length;
                }
            }
        }
        return output;
    }
share|improve this answer
    
A tiny optimisation : forstr.Length is j-i. Thus, the test forstr.Length > minimum can be rewritten j-i > minimum which is j > i + minimum. This condition is false on first iteration so either this is wrong or you can skip first iteration. Also, I think your indices i and j should go in opposite direction so that you can stop the inner loop when you find a palindrom. –  Josay Mar 6 '14 at 9:27

For what its worth, here is another algorithm. It tries to find the largest palindrome by searching for the largest possible palindrome first, and if not found, gradually for smaller ones. Not tested for speed but should be significantly faster.

static string FindLargestPalindrome(string data, int minLength) {
    int length = data.Length;

    // test from max length to min length
    for (int size = length; size >= minLength; --size)
        // establish attempt bounds and test for the first palindrome substring of given size
        for (int attemptIdx = 0, attemptIdxEnd = length - size + 1; attemptIdx < attemptIdxEnd; ++attemptIdx)
            if (IsPalindrome(data, attemptIdx, size))
                return data.Substring(attemptIdx, size);

    return null;
}

static bool IsPalindrome(string data, int idxStart, int count) {
    int idxEnd = idxStart+count-1;

    while (idxStart < idxEnd && data[idxStart] == data[idxEnd]) {
        ++idxStart;
        --idxEnd;
    }

    return idxStart >= idxEnd;
}
share|improve this answer
    
It is a good idea. Can you reformat the code to make it readable? –  Love Mar 7 '14 at 14:33
    
Thanks for recognizing the algorithm idea. Feel free to reformat the code at you end, based on your personal preferences and readability criteria. –  hocho Mar 7 '14 at 16:48
    
Not a review, It's a code dump –  JaDogg Apr 27 at 18:28

With all due respect to solutions offered, the solutions offered here are naive (naive in the sense of something that someone unfamiliar with computer science algorithms would think of). The most optimal solution will most probably be implemented using a dynamic programming approach (at the risk of stating the obvious I must emphasize that dynamic programming is not a language but an algorithmic concept that can be implemented in any language) where the program recursively finds smaller palindromes and combines them into larger ones when possible. The main problem with solutions offered here is that many sub-problems (which are essentially the same) are computed over and over and over and over again (you get the idea).

Actually, I just did a search for this and an elegant solution using dynamic programming is offered here. :)

share|improve this answer
    
Links can rot, please incorporate the main points from your link into the answer. –  Nick Udell Apr 28 at 10:32
    
The gist of my comment is that this problem has an elegant solution using dynamic programming approach. I would not be able to do justice to dynamic programming or the solution to this problem using that approach in this context. In case of a rotted link, I suggest that interested reader do a search on "dynamic programming" + "finding the largest palindrome". –  Jack Jones Apr 28 at 10:52

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.