Find the longest palindromic substring.
#include <string.h>
/* returns length; *start receives the starting index */
size_t longest_palindrome(const char *s, size_t *start)
{
size_t n = strlen(s), best = n ? 1 : 0;
*start = 0;
for (size_t c = 0; c < n; c++) {
for (int odd = 1; odd >= 0; odd--) { /* odd and even length centres */
long lo = (long)c, hi = (long)c + (odd ? 0 : 1);
while (lo >= 0 && hi < (long)n && s[lo] == s[hi]) { lo--; hi++; }
size_t len = (size_t)(hi - lo - 1);
if (len > best) { best = len; *start = (size_t)(lo + 1); }
}
}
return best;
}
/* "babad" -> 3 ("bab"), "cbbd" -> 2 ("bb") */
Points: expand around every centre (2n − 1 centres: characters and gaps between them); O(n²) time, O(1) space, simple enough for an interview. Manacher's algorithm does it in O(n) if asked.