One way to search for palindromic substrings is to consider strings with odd and even lengths separately.

A string may contain palindromes with either odd or even lengths. For example, the string CATTACAT includes the odd-length palindrome TACAT and the even-length palindrome CATTAC. In both cases, the palindrome is symmetric around its center, and the pieces on the two sides of the center are reverses of each other.

For an odd-length palindrome, the center is the middle letter. In the palindrome TACAT, the center is the C, the left side is TA, and the right side is AT.

For an even-length palindrome, the center is the border between two letters. In the palindrome CATTAC, the center is the border between the two Ts, the left side is CAT, and the right side is TAC.

All of this suggests a method for finding palindromes. To find odd-length palindromes, start at the center letter. Then, consider the letters one position to the left and right of the center. If they are the same, consider the letters two positions to the left and right of the center. Continue expanding out from the center until the corresponding letters do not match or you reach one of the ends of the string.

The method for finding an even-length palindrome is similar, except the center is between letters instead of on a letter.

The following code shows a helper method that uses this technique to return the longest palindrome with a given center position:

// Return the longest palindromic substring with center
// between start and end.
private static string LongestPalAt(string input, int start, int end)
{
    while ((start >= 0) && (end < input.Length) &&
        (input[start] == input[end]))
    {
        start--;
        end++;
    }
    return input.Substring(start + 1, end - start - 1);
}

The parameters start and end indicate the first letters on the left and right sides of the center, whether that center is on a letter or a border between letters.

As long as the start and end indices lie within the string, and as long as the characters at those positions match, the code expands the search.

After the loop ends, the start and end values point one position beyond the ends of the longest palindrome at this position. The method uses the string's Substring method to pull out the palindrome and returns it.

The following method uses the LongestPalAt helper method to find the longest palindromic substring within a string:

// Return the longest palindromic substring in this string.
public static string LongestPalindromicSubstring(this string input)
{
    // Remove punctuation and spaces and convert to uppercase.
    input = input.RemovePunctuation().Replace(" ", "").ToUpper();

    // Start with the first character as the longest palindromic 
    // substring.
    string bestPal = input.Substring(0, 1);
    int bestLength = 1;

    // Look for odd-length palindromes.
    int inputLength = input.Length;
    for (int i = 1; i < inputLength; i++)
    {
        string testPal = LongestPalAt(input, i, i);
        if (testPal.Length > bestLength)
        {
            bestPal = testPal;
            bestLength = bestPal.Length;
        }
    }

    // Look for even-length palindromes.
    for (int i = 1; i < inputLength; i++)
    {
        string testPal = LongestPalAt(input, i - 1, i);
        if (testPal.Length > bestLength)
        {
            bestPal = testPal;
            bestLength = bestPal.Length;
        }
    }

    return bestPal;
}

The method first uses the RemovePunctuation method that was created in the preceding solution to remove punctuation characters from the input. It also removes spaces and converts the string into uppercase.

Next, the code saves the string's first letter as the best palindrome it has found so far. (Any single character is a palindrome.)

The code then loops over the string's character positions and uses LongestPalAt to get the longest palindrome centered around each letter's position. If that palindrome is longer than the longest one found so far, the method saves the new palindrome.

Next, the code repeats those steps to look for even-length palindromes.

After it finishes checking for palindromes at each letter's position and between each pair of letters, the method returns the longest palindrome that it found.

Download the PalindromicSubstrings example solution to see additional details.