Longest Palindrome in a String (Solution)

I'm going to pull solutions from all over the web. StackOverflow has always been a huge help to me, and I hope to leverage it here as well.

Here are some solutions and here is a nice explanation from Steve Krenzel.

This is one easy-to-read solution from Mohit Bhandari:

public static string GetPalindromeString(string theInputString)
 { 
        int j = 0;
        int k = 0;
        string aPalindrome = string.Empty;
        string aLongestPalindrome = string.Empty ;          
        for (int i = 1; i < theInputString.Length; i++)
        {
            k = i + 1;
            j = i - 1;
            while (j >= 0 && k < theInputString.Length)
            {
                if (theInputString[j] != theInputString[k])
                {
                    break;
                }
                else
                {
                    j--;
                    k++;
                }
                aPalindrome = theInputString.Substring(j + 1, k - j - 1);
                if (aPalindrome.Length > aLongestPalindrome.Length)
                {
                    aLongestPalindrome = aPalindrome;
                }
            }
        }
        return aLongestPalindrome;     
  }

It should be noted that the above method does not work if the palindrome is of even length. To handle that case, the code would need to be modified such that j or k starts at i, rather than i +/- 1.

This algorithm runs in O(n^2) time.

Longest Palindrome in a String

Let's start with a classic!

Given a string, write a function that returns the longest palindrome in that string.  For example:

Input: "A racecar goes fast.  Toyota.  Honda.  They're both good."
Output: "racecar"

Some things to consider are:

• What happens if the palindrome has an even number of characters?
• What kind of time complexity can we get?

A solution will be posted in a few days!