1. 8
  1.  

  2. 8

    This can actually be done in linear time, as I wrote about long ago: https://www.akalin.com/longest-palindrome-linear-time

    There’s no way I’d expect someone to know/come up with Manacher’s algorithm (as the linear-time algorithm is known) in an interview setting, though.