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

2 Answers 2

up vote 7 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 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 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 at 16:48

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.