Longest palindromic substring

Try every index as the center of a palindrome and expand outward while the characters match, once for an odd-length center and once for an even-length center.

The idea

A palindrome is defined by its center. Every center is either a single character (odd length) or the gap between two characters (even length). Expanding outward from a center while the two sides keep matching finds the longest palindrome centered there in O(n) time, and trying all 2n-1 centers covers every possible palindrome.

Code

public static string LongestPalindrome(string s) {
    int bestStart = 0, bestLen = 1;
    for (int center = 0; center < s.Length; center++) {
        int len1 = Expand(s, center, center);
        int len2 = Expand(s, center, center + 1);
        int len = Math.Max(len1, len2);
        if (len > bestLen) { bestLen = len; bestStart = center - (len - 1) / 2; }
    }
    return s.Substring(bestStart, bestLen);
}

static int Expand(string s, int l, int r) {
    while (l >= 0 && r < s.Length && s[l] == s[r]) { l--; r++; }
    return r - l - 1;
}

Tips

• len1 handles odd-length palindromes like "aba"; len2 handles even-length ones like "abba".
• bestStart = center - (len - 1) / 2 works for both cases because integer division rounds the odd case down correctly.

In the .NET library

Expanding from centers is simpler to code correctly than Manacher's O(n) algorithm, and is the answer most interviews expect for this problem.