</>EmbeddedInterview

Find the longest palindromic substring.

Medium"Coding: Memory & String Functions"
#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.