Return the largest palindrome from the string

Question

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; 
}

Answer 1

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 = 2;
    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;
}

EDIT

The above code has a bug. Here it is reworked:

static string LargestPalindrome(string input)
{
    int longest = 0;
    int limit = input.Length;
    for (int i = 0; i < limit; i++)
    {
        for (int j = limit-1; j > i; j--)
        {
            string forStr = input.Substring(i, j - i);
            string revStr = new string(forStr.Reverse().ToArray());
            if (forStr == revStr && forStr.Length > longest)
            {
                return forStr;
            }
        }
    }
    return "";
}

Answer 2

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;
}

Answer 3

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. :)