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

• SylvainD: 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.
• Haney: This code (the final code block in the answer) is broken on the input of "addcdxddf" in my testing, returns empty string when it should return "dcd".
• user33306: @Haney - The challenge I made it for wouldn't accept a palindrome length of less than 4. I've edited it to accept palindromes of 3 characters.
• Love: Although I marked it as an answer. But after many years, I test it again. It failed for the string cbbd. The expected answer is bb.
• user33306: @Love - As per my comment to Haney, this code isn't designed to find palindromes of less than 3 characters

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

• Love: It is a good idea. Can you reformat the code to make it readable?
• hocho: Thanks for recognizing the algorithm idea. Feel free to reformat the code at you end, based on your personal preferences and readability criteria.
• JaDogg: Not a review, It's a code dump

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

• Nick Udell: Links can rot, please incorporate the main points from your link into the answer.
• Jack Jones: 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".